Robust Assignments via Ear Decompositions and Randomized Rounding

DOI10.4230/LIPIcs.ICALP.2016.71zbMath1388.90062arXiv1607.02437OpenAlexW2963005543MaRDI QIDQ4598211

Viktor Bindewald, David Adjiashvili, Dennis Michaels

Publication date: 19 December 2017

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

zbMATH Keywords

approximation algorithmrobust optimizationrandomized roundingear decompositionmatching theory

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

Robust combinatorial optimization under convex and discrete cost uncertainty ⋮ How to Secure Matchings against Edge Failures ⋮ Minimum \(k\)-critical bipartite graphs ⋮ How to Secure Matchings Against Edge Failures

This page was built for publication: Robust Assignments via Ear Decompositions and Randomized Rounding