Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More

Mihail Stoian

Despite much research, hard weighted problems still resist super-polynomial improvements over their textbook solution. On the other hand, the unweighted versions of these problems…