Approximability and Exact Resolution of the Multidimensional Binary Vector Assignment Problem
Publication:2835671
DOI10.1007/978-3-319-45587-7_13zbMath1471.90168MaRDI QIDQ2835671
Marin Bougeret, Rodolphe Giroudeau, Guillerme Duvillié
Publication date: 30 November 2016
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://dipot.ulb.ac.be/dspace/bitstream/2013/307765/3/JOCO_2017_approx_and_exact_resolution_bMVA.pdf
NP-hardness; approximation scheme; APX-hardness; unique games conjecture; exact resolution; vector assignment problem
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
90C60: Abstract computational complexity for mathematical programming problems
90C59: Approximation methods and heuristics in mathematical programming
03D15: Complexity of computation (including implicit computational complexity)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms