Algorithms to Approximate Column-sparse Packing Problems

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 Füredi, Kahn, and Seymour on hypergraph matching (Combinatorica, 1993).

• Publication year

  2017

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2017-11-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/3355400arXiv 1711.02724
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• D S ] 5 A ug 2 01 9 Algorithms to Approximate Column-Sparse Packing Problems ∗

  2019cited by this paper
• Random Order Contention Resolution Schemes

  2018cited by this paper
• Random Walks in Polytopes and Negative Dependence

  2017cited by this paper
• Improved Bounds in Stochastic Matching and Optimization

  2017cited by this paper
• Attenuate Locally, Win Globally: An Attenuation-based Framework for Online Stochastic Matching with Timeouts

  2017cited by this paper
• Constrained Submodular Maximization via a Non-symmetric Technique

  2016cited by this paper
• Algorithms and Adaptivity Gaps for Stochastic Probing

  2016cited by this paper
• Constrained Submodular Maximization: Beyond 1/e

  2016cited by this paper
• An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound

  2016cited by this paper
• Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems

  2016cited by this paper
• Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions

  2016cited by this paper
• Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method

  2016cited by this paper
• On Multiplicative Weight Updates for Concave and Submodular Function Maximization

  2015cited by this paper
• Improved Approximation Algorithms for Stochastic Matching

  2015cited by this paper
• Non-negative submodular stochastic probing via stochastic contention resolution schemes

  2015influential reference
• Discrepancy Without Partial Colorings

  2014cited by this paper
• Constructive Discrepancy Minimization for Convex Sets

  2014cited by this paper
• Generalized Hypergraph Matching via Iterated Packing and Local Ratio

  2014cited by this paper
• Submodular Maximization with Cardinality Constraints

  2014cited by this paper
• Submodular Stochastic Probing on Matroids

  2013cited by this paper
• Stochastic combinatorial optimization via poisson approximation

  2012cited by this paper
• Solving Packing Integer Programs via Randomized Rounding with Alterations

  2012cited by this paper
• Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees

  2012cited by this paper
• Constructive Discrepancy Minimization by Walking on the Edges

  2012cited by this paper
• A Unified Continuous Greedy Algorithm for Submodular Maximization

  2011cited by this paper
• Submodular function maximization via the multilinear relaxation and contention resolution schemes

  2011influential reference
• Deterministic Discrepancy Minimization

  2011cited by this paper
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

  2011cited by this paper
• Iterative Packing for Demand and Hypergraph Matching

  2011cited by this paper
• A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems

  2011influential reference
• Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures

  2010cited by this paper
• When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings

  2010cited by this paper
• On linear and semidefinite programming relaxations for hypergraph matching

  2010influential reference
• Constructive Algorithms for Discrepancy Minimization

  2010cited by this paper
• Submodular maximization by simulated annealing

  2010influential reference
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs

  2009cited by this paper
• Approximability of Sparse Integer Programs

  2009cited by this paper
• A logarithmic approximation for unsplittable flow on line graphs

  2009cited by this paper
• Maximizing submodular set functions subject to multiple linear constraints

  2009cited by this paper
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints

  2009cited by this paper
• Optimal approximation for the submodular welfare problem in the value oracle model

  2008cited by this paper
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

  2008cited by this paper
• Multicommodity demand flow in a tree and packing integer programs

  2007cited by this paper
• On the complexity of approximating k-set packing

  2006cited by this paper
• Linear degree extractors and the inapproximability of max clique and chromatic number

  2006cited by this paper
• A quasi-PTAS for unsplittable flow on line graphs

  2006influential reference
• An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow

  2006influential reference
• Combinatorial Algorithms for the Unsplittable Flow Problem

  2005influential reference
• Adaptivity and approximation for stochastic packing problems

  2005cited by this paper
• Approximating the stochastic knapsack problem: the benefit of adaptivity

  2004cited by this paper
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

  2004influential reference
• Approximating disjoint-path problems using packing integer programs

  2004cited by this paper
• A note on the greedy algorithm for the unsplittable flow problem

  2003cited by this paper
• New algorithmic aspects of the Local Lemma with applications to routing and partitioning

  2002cited by this paper
• Improved bounds for the unsplittable flow problem

  2002influential reference
• Randomized metarounding

  2002cited by this paper
• Approximation Algorithms for the Unsplittable Flow Problem

  2002cited by this paper
• Greedy local improvement and weighted set packing approximation

  2001cited by this paper
• A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs

  2000cited by this paper
• Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems

  2000cited by this paper
• Improved Approximation Guarantees for Packing and Covering Integer Programs

  1999influential reference
• On Local Search for Weighted k-Set Packing

  1997cited by this paper
• Primal-dual approximation algorithms for integral flow and multicut in trees

  1997influential reference
• Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems

  1997cited by this paper
• Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds

  1997cited by this paper
• Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems

  1997cited by this paper
• Approximation algorithms for disjoint paths problems

  1996influential reference
• Chernoff-Hoeffding bounds for applications with limited independence

  1995cited by this paper
• On the fractional matching polytope of a hypergraph

  1993influential reference
• On the Size of Systems of Sets Every t of Which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems

  1989cited by this paper
• On a Packing and Covering Problem

  1985cited by this paper
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory

  1982influential reference
• "Integer-making" theorems

  1981cited by this paper
• A Note on Ramsey Numbers

  1980cited by this paper
• An analysis of approximations for maximizing submodular set functions—I

  1978cited by this paper
• An inequality for the chromatic number of a graph

  1968cited by this paper
• Decomposition of Finite Graphs Into Forests

  1964cited by this paper
• HOW TO ORIENT THE EDGES OF A GRAPH?

  year unknowninfluential reference

• Barter Exchange with Shared Item Valuations

  2024cites this paper
• On contention resolution for the hypergraph matching, knapsack, and k-column sparse packing problems

  2024influential citation
• Group Fairness in Set Packing Problems

  2023influential citation
• Approximation Algorithms for Cost-robust Discrete Minimization Problems Based on their LP-Relaxations

  2022cites this paper
• Exploring the Tradeoff between Competitive Ratio and Variance in Online-Matching Markets

  2022cites this paper
• Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture

  2020cites this paper
• Simpler and Stronger Approaches for Non-Uniform Hypergraph Matching and the Füredi, Kahn, and Seymour Conjecture

  2020influential citation
• Improved Approximation Algorithms for Stochastic-Matching Problems

  2020cites this paper
• Scheduling split intervals with non-uniform demands

  2020cites this paper
• SIGecom job market candidate profiles 2019

  2019cites this paper
• Random Order Contention Resolution Schemes

  2018cites this paper
• D S ] 7 A pr 2 01 8 Random Order Contention Resolution Schemes

  2018cites this paper