Integrality gaps for colorful matchings
From MaRDI portal
Publication:2419586
DOI10.1016/j.disopt.2018.12.003zbMath1506.90261arXiv1801.07937OpenAlexW2911187972WikidataQ128507779 ScholiaQ128507779MaRDI QIDQ2419586
Georgios Stamoulis, Steven Kelk
Publication date: 14 June 2019
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1801.07937
Programming involving graphs or networks (90C35) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy
- On linear and semidefinite programming relaxations for hypergraph matching
- Maximum transversal in partial Latin squares and rainbow matchings
- Matching is as easy as matrix inversion
- Maximum degree and fractional matchings in uniform hypergraphs
- An \(n\times n\) Latin square has a transversal with at least \(n-\sqrt n\) distinct symbols
- Lift and project relaxations for the matching and related polytopes
- Matchings in colored bipartite networks
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Almost exact matchings
- Bi-criteria and approximation algorithms for restricted matchings
- Maximum weight edge-constrained matchings
- Complexity results for rainbow matchings
- On a Representation of the Matching Polytope Via Semidefinite Liftings
- An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
- Lift-and-Project Methods for Set Cover and Knapsack
- Approximation Algorithms for Bounded Color Matchings via Convex Decompositions
- New approximation guarantee for chromatic number
- Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
- Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
- Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
- Iterative Packing for Demand and Hypergraph Matching
- Iterative Methods in Combinatorial Optimization
- Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Generalized Hypergraph Matching via Iterated Packing and Local Ratio
- Randomized and Approximation Algorithms for Blue-Red Matching
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Approximating Sparsest Cut in Graphs of Bounded Treewidth
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- The complexity of restricted spanning tree problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Some Matching Problems for Bipartite Graphs
- Maximum matching of given weight in complete and complete bipartite graphs
- Subset Algebra Lift Operators for 0-1 Integer Programming
- Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
- Sherali-adams relaxations of the matching polytope
- MaxMin allocation via degree lower-bounded arborescences
- Transversals in Latin Squares
- Greedy in Approximation Algorithms
- Sparsest cut on bounded treewidth graphs
- Maximum matching and a polyhedron with 0,1-vertices
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Wavelength Management in WDM Rings to Maximize the Number of Connections
This page was built for publication: Integrality gaps for colorful matchings
