Back to Search
Start Over
Approximating the discrete time-cost tradeoff problem with bounded depth.
- Source :
-
Mathematical Programming . Feb2023, Vol. 197 Issue 2, p529-547. 19p. - Publication Year :
- 2023
-
Abstract
- We revisit the deadline version of the discrete time-cost tradeoff problem for the special case of bounded depth. Such instances occur for example in VLSI design. The depth of an instance is the number of jobs in a longest chain and is denoted by d. We prove new upper and lower bounds on the approximability. First we observe that the problem can be regarded as a special case of finding a minimum-weight vertex cover in a d-partite hypergraph. Next, we study the natural LP relaxation, which can be solved in polynomial time for fixed d and—for time-cost tradeoff instances—up to an arbitrarily small error in general. Improving on prior work of Lovász and of Aharoni, Holzman and Krivelevich, we describe a deterministic algorithm with approximation ratio slightly less than d 2 for minimum-weight vertex cover in d-partite hypergraphs for fixed d and given d-partition. This is tight and yields also a d 2 -approximation algorithm for general time-cost tradeoff instances, even if d is not fixed. We also study the inapproximability and show that no better approximation ratio than d + 2 4 is possible, assuming the Unique Games Conjecture and P ≠ NP . This strengthens a result of Svensson [21], who showed that under the same assumptions no constant-factor approximation algorithm exists for general time-cost tradeoff instances (of unbounded depth). Previously, only APX-hardness was known for bounded depth. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 197
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 161716888
- Full Text :
- https://doi.org/10.1007/s10107-022-01777-9