Approximability and exact resolution of the multidimensional binary vector assignment problem

DOI10.1007/978-3-319-45587-7_13MaRDI QIDQ2835671zbMATH OpenOpenAlexFDO

Authors Marin Bougeret, Guillerme Duvillié, Rodolphe Giroudeau

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

approximation schemeAPX-hardnessexact resolutionNP-hardnessunique games conjecturevector assignment problem

Mathematics Subject Classification ID

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

Recommendations

• Approximability and exact resolution of the multidimensional binary vector assignment problem
• Multi-dimensional vector assignment problems
• scientific article; zbMATH DE number 1305407

Cites work

• Approximation algorithms for the wafer to wafer integration problem
• Inapproximability of hypergraph vertex cover and applications to scheduling problems
• Multi-dimensional vector assignment problems
• On the complexity of wafer-to-wafer integration
• Reductions, completeness and the hardness of approximability

Cited in

(4)

• Approximability and exact resolution of the multidimensional binary vector assignment problem
• Multi-dimensional vector assignment problems
• Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms
• Exploiting hidden structure in selecting dimensions that distinguish vectors

This page was built for publication: Approximability and exact resolution of the multidimensional binary vector assignment problem

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