Jansen, Klaus, Land, F. and Land, K. (2016) BOUNDING THE RUNNING TIME OF ALGORITHMS FOR SCHEDULING AND PACKING PROBLEMS. Siam Journal on Discrete Mathematics, 8037 (1). pp. 343-366. DOI 10.1007/978-3-642-40104-6_38.

Full text not available from this repository.

Abstract

Our goal is to show tight bounds on the running time of algorithms for scheduling and packing problems. To prove lower bounds, we investigate implications of the exponential time hypothesis on such algorithms. For exact algorithms we consider the dependence of the running time on the number n of items (for packing) or jobs (for scheduling). We prove a lower bound of 2(o(n)) x vertical bar vertical bar I vertical bar vertical bar(O(n)), where vertical bar vertical bar I vertical bar vertical bar denotes the encoding length of the instance, for several of these problems, including SUBSETSUM, KNAPSACK, BINPACKING, < P2 vertical bar vertical bar C-max >, and < P2 vertical bar vertical bar Sigma w(j)C(j)>. We also develop an algorithmic framework that is able to solve a large number of scheduling and packing problems in time 2o(n) x vertical bar vertical bar I vertical bar vertical bar(O(n)). Finally, we consider approximation schemes. We show that there is no polynomial time approximation scheme for MULTIPLEKNAPSACK (MKS) and 2D-KNAPSACK with running time 2(o(1/epsilon)) x vertical bar vertical bar I vertical bar vertical bar(O(n)) and n(o(1/epsilon)) x vertical bar vertical bar I vertical bar vertical bar(O(n)), respectively.

Document Type:	Article
Additional Information:	Times Cited: 0 Jansen, K. Land, F. Land, K.
Keywords:	scheduling, packing, exponential time hypothesis, exact algorithms, lower bounds
Research affiliation:	Kiel University > Kiel Marine Science OceanRep > The Future Ocean - Cluster of Excellence Kiel University
Refereed:	Yes
Open Access Journal?:	No
Publisher:	American Medical Association
Projects:	Future Ocean
Date Deposited:	24 Feb 2017 13:55
Last Modified:	26 Aug 2019 07:54
URI:	https://oceanrep.geomar.de/id/eprint/36154

Actions (login required)

View Item