Bounding the Running Time of Algorithms for Scheduling and Packing Problems

We investigate the implications of the exponential time hypothesis on algorithms for scheduling and packing problems. Our main focus is to show tight lower bounds on the running time of these algorithms. For exact algorithms we investigate the dependence of the running time on the number n of items (for packing) or jobs (for scheduling). We show that many of these problems, including SUBSET SUM, KNAPSACK, BIN PACKING, P2||Cmax, and P2||∑wjCj, have a lower bound of 2o(n)×∥I∥O(n). We also develop an algorithmic framework that is able to solve a large number of scheduling and packing problems in time 2O(n)×∥I∥O(n). Finally, we show that there is no PTAS for MULTIPLE KNAPSACK and 2D-KNAPSACK with running time 2o(1ε)×∥I∥O(n) and no(1ε)×∥I∥O(n).

Logo BII

BII

Rechte

Nutzung und Vervielfältigung:

Keine Lizenz. Es gelten die Bestimmungen des deutschen Urheberrechts (UrhG).

Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.