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

APX-hardnessNP-hardnessunique games conjectureapproximation schemeexact resolutionvector assignment problem

Mathematics Subject Classification ID

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

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
• Exploiting hidden structure in selecting dimensions that distinguish vectors
• Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms

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)