A new rounding procedure for the assignment problem with applications to dense graph arrangement problems

DOI10.1007/S101070100271zbMath1154.90602OpenAlexW1965193466WikidataQ57401523 ScholiaQ57401523MaRDI QIDQ1600093

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

zbMATH Keywords

additive approximation algorithmPolynomial Time Approximation Schemesrandomized procedure for rounding fractional perfect matchings to integral matchings

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Discrete location and assignment (90B80)

Related Items (24)

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