Approximability and Exact Resolution of the Multidimensional Binary Vector Assignment Problem

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

zbMATH Keywords

NP-hardness; approximation scheme; APX-hardness; unique games conjecture; exact resolution; vector assignment problem

Mathematics Subject Classification ID

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