Improved Approximation Guarantees for Packing and Covering Integer Programs
From MaRDI portal
Publication:4943764
DOI10.1137/S0097539796314240zbMath1032.90029MaRDI QIDQ4943764
Publication date: 19 March 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
linear programminginteger programmingcombinatorial optimizationcorrelation inequalitiesapproximation algorithmsderandomizationrandomized roundingpacking integer programslinear relaxationscovering integer programspositive correlationrounding theorems
Related Items (27)
Sensitivity-Informed Provable Pruning of Neural Networks ⋮ On the approximability of clique and related maximization problems ⋮ Local ratio method on partial set multi-cover ⋮ Approximations for generalized unsplittable flow on paths with application to power systems optimization ⋮ Approximation Algorithms for Stochastic and Risk-Averse Optimization ⋮ Approximating covering integer programs with multiplicity constraints ⋮ Approximability of sparse integer programs ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Approximation of set multi-cover via hypergraph matching ⋮ Approximation schemes for deal splitting and covering integer programs with multiplicity constraints ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ Parameterized Dynamic Variants of Red-Blue Dominating Set ⋮ Distributed approximation of \(k\)-service assignment ⋮ Approximation algorithm for partial positive influence problem in social network ⋮ Lower bounds and algorithms for the minimum cardinality bin covering problem ⋮ Non-independent randomized rounding and coloring ⋮ Dynamic programming based algorithms for set multicover and multiset multicover problems ⋮ A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership ⋮ Approximating Sparse Covering Integer Programs Online ⋮ Aggregation-based cutting-planes for packing and covering integer programs ⋮ Inapproximability of b-Matching in k-Uniform Hypergraphs ⋮ \(\ell_1\)-sparsity approximation bounds for packing integer programs ⋮ On interval and circular-arc covering problems ⋮ Approximation algorithms for covering/packing integer programs ⋮ Unnamed Item ⋮ Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations ⋮ Stochastic makespan minimization in structured set systems
This page was built for publication: Improved Approximation Guarantees for Packing and Covering Integer Programs
