A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
From MaRDI portal
Publication:1600093
DOI10.1007/s101070100271zbMath1154.90602OpenAlexW1965193466WikidataQ57401523 ScholiaQ57401523MaRDI QIDQ1600093
Sanjeev Arora, Haim Kaplan, Alan M. Frieze
Publication date: 12 June 2002
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s101070100271
additive approximation algorithmPolynomial Time Approximation Schemesrandomized procedure for rounding fractional perfect matchings to integral matchings
Related Items
Efficient reassembling of graphs. I: The linear case ⋮ Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges ⋮ Approximate and dynamic rank aggregation ⋮ A survey for the quadratic assignment problem ⋮ Additive approximation for edge-deletion problems ⋮ A survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Approximating combinatorial optimization problems with the ordered weighted averaging criterion ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming ⋮ On the complexity of compressing two dimensional routing tables with order ⋮ Minimum-weight combinatorial structures under random cost-constraints ⋮ On the approximation of correlation clustering and consensus clustering ⋮ Graph Similarity and Approximate Isomorphism ⋮ Selected topics on assignment problems ⋮ An updated survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem ⋮ Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles ⋮ Randomized Rounding in the Presence of a Cardinality Constraint ⋮ Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines ⋮ Tournaments and Semicomplete Digraphs ⋮ Concentration inequalities for nonlinear matroid intersection ⋮ Unnamed Item ⋮ The Approximate Loebl--Komlós--Sós Conjecture I: The Sparse Decomposition ⋮ On an ordering problem in weighted hypergraphs
This page was built for publication: A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
