Iterative Packing for Demand and Hypergraph Matching

DOI10.1007/978-3-642-20807-2_28zbMath1341.90116arXiv1604.00310OpenAlexW37721340MaRDI QIDQ3009775

Ojas Parekh

Publication date: 24 June 2011

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

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

Mathematics Subject Classification ID

Hypergraphs (05C65) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Matching models (91B68)

Related Items (7)

Constant factor approximation for the weighted partial degree bounded edge packing problem ⋮ Generalized Hypergraph Matching via Iterated Packing and Local Ratio ⋮ Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope ⋮ Integrality gaps for colorful matchings ⋮ Stochastic packing integer programs with few queries ⋮ Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation

Cites Work

• Unnamed Item
• Approximability of sparse integer programs
• On the fractional matching polytope of a hypergraph
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Approximating disjoint-path problems using packing integer programs
• On the complexity of approximating \(k\)-set packing
• Approximating minimum bounded degree spanning trees to within one of optimal
• On k-Column Sparse Packing Programs
• Multicommodity demand flow in a tree and packing integer programs
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
• Approximability of Sparse Integer Programs
• Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
• Randomized metarounding
• The Demand-Matching Problem
• Scheduling Split Intervals
• Mathematical Foundations of Computer Science 2005

This page was built for publication: Iterative Packing for Demand and Hypergraph Matching