REAL

Reductions between scheduling problems with non-renewable resources and knapsack problems

Györgyi, Péter and Kis, Tamás (2015) Reductions between scheduling problems with non-renewable resources and knapsack problems. THEORETICAL COMPUTER SCIENCE, 565 (2). pp. 63-76. ISSN 0304-3975

This is the latest version of this item.

[img]
Preview
Text
r1.pdf

Download (452kB) | Preview

Abstract

In this paper we establish approximation preserving reductions between scheduling problems in which jobs either consume some raw materials, or produce some intermediate products, and variants of the knapsack problem. Through the reductions, we get new approximation algorithms, as well as inapproximability results for the scheduling problems.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Dr. Tamás Kis
Date Deposited: 17 Nov 2015 09:22
Last Modified: 04 Apr 2023 11:17
URI: http://real.mtak.hu/id/eprint/30240

Available Versions of this Item

Actions (login required)

Edit Item Edit Item