Algorithms to approximate column-sparse packing problems

DOI10.1145/3355400MaRDI QIDQ4973058zbMATH OpenOpenAlexWikidataFDO

Authors Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, Pan Xu

Publication date 2 December 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

randomized algorithmsapproximation algorithmspacking programs

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25) Integer programming (90C10)

Abstract: Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and multiple-chance algorithms, to obtain improved approximation algorithms for some well-known families of such problems. As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations for k-column sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic k-set packing (Bansal et al., Algorithmica, 2012), and go "half the remaining distance" to optimal for a major integrality-gap conjecture of Furedi, Kahn and Seymour on hypergraph matching (Combinatorica, 1993).

Recommendations

• scientific article; zbMATH DE number 6850331
• On k-column sparse packing programs
• Approximating low-congestion routing and column-restricted packing problems
• Solving packing integer programs via randomized rounding with alterations
• Approximability of Sparse Integer Programs

Cited in

(8)

• Column basis reduction and decomposable knapsack problems
• Approximating low-congestion routing and column-restricted packing problems
• Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems
• Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture
• Iterative packing for demand and hypergraph matching
• On k-column sparse packing programs
• scientific article; zbMATH DE number 6850331 (Why is no real title available?)
• Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations

This page was built for publication: Algorithms to approximate column-sparse packing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4973058)