Approximating the discrete time-cost tradeoff problem with bounded depth

DOI10.1007/978-3-030-73879-2_3zbMath1482.90179arXiv2011.02446OpenAlexW3162050930MaRDI QIDQ5918419

Siad Daboul, Stephan Held, Jens Vygen

Publication date: 21 December 2021

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2011.02446

zbMATH Keywords

minimum-weight vertex cover, natural LP relaxation, constant-factor approximation algorithm

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• Project scheduling with irregular costs: complexity, approximability, and algorithms
• A class of simple games
• On the hardness of approximating minimum vertex cover
• Some APX-completeness results for cubic graphs
• Hardness of approximation of the discrete time-cost tradeoff problem
• On a theorem of Lovász on covers in \(r\)-partite hypergraphs
• Minimum \(k\)-path vertex cover
• Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem
• Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs
• A linear-time approximation algorithm for the weighted vertex cover problem
• Complexity of the Discrete Time-Cost Tradeoff Problem for Project Networks
• Bottleneck extrema