On linear and semidefinite programming relaxations for hypergraph matching
From MaRDI portal
Publication:715088
DOI10.1007/S10107-011-0451-5zbMATH Open1254.90107OpenAlexW3136714316MaRDI QIDQ715088FDOQ715088
Authors: Yuk Hei Chan, Lap Chi Lau 
Publication date: 15 October 2012
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-011-0451-5
Recommendations
Linear programming (90C05) Combinatorial optimization (90C27) Semidefinite programming (90C22) Approximation algorithms (68W25) Hypergraphs (05C65)
Cites Work
- Geometric algorithms and combinatorial optimization
- On the Shannon capacity of a graph
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- The ellipsoid method and its consequences in combinatorial optimization
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Non-approximability results for optimization problems on bounded degree instances
- On the facial structure of set packing polyhedra
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Title not available (Why is that?)
- Ryser's conjecture for tripartite 3-graphs
- Title not available (Why is that?)
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- On the complexity of approximating \(k\)-set packing
- A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs
- The sandwich theorem
- The Santa Claus problem
- 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
- Integrality gaps for Sherali-Adams relaxations
- Sherali-Adams relaxations of the matching polytope
- Scheduling Split Intervals
- Hall's theorem for hypergraphs
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Approximating the independence number via the \(\vartheta\)-function
- Randomized graph products, chromatic numbers, and Lovasz j-function
- Critical hypergraphs and interesting set-pair systems
- Maximum degree and fractional matchings in uniform hypergraphs
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- An approximation algorithm for maximum triangle packing
- Title not available (Why is that?)
- Tree-width and the Sherali-Adams operator
- Santa Claus Meets Hypergraph Matchings
- On local search for weighted \(k\)-set packing
- Title not available (Why is that?)
- On Completing Latin Squares
- On the fractional matching polytope of a hypergraph
- On two intersecting set systems and k-continuous Boolean functions
- Local global tradeoffs in metric embeddings
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- CSP gaps and reductions in the lasserre hierarchy
- The Lovász Number of Random Graphs
- Title not available (Why is that?)
- On the complexity of approximating \(k\)-dimensional matching
- Approximation algorithms and hardness results for the clique packing problem
Cited In (23)
- Technical note -- Online hypergraph matching with delays
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Online crowdsourced truck delivery using historical information
- Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
- On the parameterized complexity of compact set packing
- Coverage, matching, and beyond: new results on budgeted mechanism design
- Approximate multi-matroid intersection via iterative refinement
- A \(\frac{1}{2}\)-integral relaxation for the \(A\)-matching problem
- An approximation result for matchings in partitioned hypergraphs
- Title not available (Why is that?)
- On the parameterized complexity of compact set packing
- On the matching polynomial of hypergraphs
- On a representation of the matching polytope via semidefinite liftings
- Sherali-Adams relaxations of the matching polytope
- Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture
- Distributed algorithms for matching in hypergraphs
- How to sell hyperedges: the hypermatching assignment problem
- Generalized hypergraph matching via iterated packing and local ratio
- Greedy matching: guarantees and limitations
- Three algorithms for graph locally harmonious colouring
- Integrality gaps for colorful matchings
- An axiomatic duality framework for the theta body and related convex corners
- ThIEF: finding genome-wide trajectories of epigenetics marks
This page was built for publication: On linear and semidefinite programming relaxations for hypergraph matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q715088)
