Robust assignments via ear decompositions and randomized rounding

DOI10.4230/LIPICS.ICALP.2016.71zbMATH Open1388.90062arXiv1607.02437OpenAlexW2963005543MaRDI QIDQ4598211FDOQ4598211

Authors: David Adjiashvili, Viktor Bindewald, Dennis Michaels 

Publication date: 19 December 2017

Abstract: Many real-life planning problems require making a priori decisions before all parameters of the problem have been revealed. An important special case of such problem arises in scheduling problems, where a set of tasks needs to be assigned to the available set of machines or personnel (resources), in a way that all tasks have assigned resources, and no two tasks share the same resource. In its nominal form, the resulting computational problem becomes the emph{assignment problem} on general bipartite graphs. This paper deals with a robust variant of the assignment problem modeling situations where certain edges in the corresponding graph are emph{vulnerable} and may become unavailable after a solution has been chosen. The goal is to choose a minimum-cost collection of edges such that if any vulnerable edge becomes unavailable, the remaining part of the solution contains an assignment of all tasks. We present approximation results and hardness proofs for this type of problems, and establish several connections to well-known concepts from matching theory, robust optimization and LP-based techniques.

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

Recommendations

• Critical edges for the assignment problem: complexity and exact resolution
• Robustly assigning unstable items
• Randomized approximation and online algorithms for assignment problems
• Exact and heuristic algorithms for the interval data robust assignment problem
• The hypergraph assignment problem

zbMATH Keywords

approximation algorithmrobust optimizationmatching theoryrandomized roundingear decomposition

Mathematics Subject Classification ID

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

Cited In (5)

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

This page was built for publication: Robust assignments via ear decompositions and randomized rounding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598211)