Approximability and Exact Resolution of the Multidimensional Binary Vector Assignment Problem

DOI10.1007/978-3-319-45587-7_13zbMath1471.90168OpenAlexW2347083085MaRDI QIDQ2835671

Guillerme Duvillié, Rodolphe Giroudeau, Marin Bougeret

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-hardnessapproximation schemeAPX-hardnessunique games conjectureexact resolutionvector assignment problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Multi-dimensional vector assignment problems
• Reductions, completeness and the hardness of approximability
• Approximation Algorithms for the Wafer to Wafer Integration Problem
• On the Complexity of Wafer-to-Wafer Integration
• Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations
• Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems

This page was built for publication: Approximability and Exact Resolution of the Multidimensional Binary Vector Assignment Problem