UG-hardness to NP-hardness by Losing Half.

Amey Bhangale Subhash Khot

Published in: Theory Comput. (2022)

Keyphrases

np hardness
np hard
approximation algorithms
mixed integer
worst case analysis
special case
scheduling problem
discrete tomography
linear programming