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.
|
Text
r1.pdf Download (452kB) | Preview |
Official URL: https://dx.doi.org/10.1016/j.tcs.2014.11.007
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
-
Reductions between scheduling problems with non-renewable resources and knapsack problems. (deposited 14 Sep 2014 18:55)
-
Reductions between scheduling problems with non-renewable resources and knapsack problems. (deposited 21 Oct 2015 08:35)
- Reductions between scheduling problems with non-renewable resources and knapsack problems. (deposited 17 Nov 2015 09:22) [Currently Displayed]
-
Reductions between scheduling problems with non-renewable resources and knapsack problems. (deposited 21 Oct 2015 08:35)
Actions (login required)
![]() |
Edit Item |