Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis

Peter Jonsson, Victor Lagerkvist, Johannes Schmidt +1

Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the…