Tag Info

4

Integer programming is strongly NP-hard, thus integer programs can in general not be solved in pseudo-polynomial time. The result of Röglin and Vöcking is that, provided that the range of integers that the variables can assume is polynomially bounded, (randomized) pseudo-polynomial solvability is equivalent to polynomial smoothed complexity. Thus, general ...

3

As far as I am aware, a comparison of approximation algorithms has not been done so far with respect to smoothed analysis. There are only a few papers on smoothed analysis of approximation ratios in the first place. Maybe only loosely related: bijective analysis has been used to directly compare the competitive ratio of online algorithms (Angelopoulos, ...

3

The paper by Bläser, Panagiotou, and Rao deals with concentration of the tour produced by Christofides' algorithm. No average-case approximation ratio is claimed, except for some experimental results. The paper by Röglin and Vöcking (Math. Program., 2007) and an earlier paper by Beier and Vöcking (SIAM J. Comput., 2006) roughly state that smoothed ...

1

In 2019, the opensource LP solver GLPK does the Klee-Minty cube problem with $D=200$ in under 100 milliseconds, on a 2.7 GHz iMac: GLPK Simplex Optimizer, v4.65 200 rows, 200 columns, 20100 non-zeros Preprocessing... 199 rows, 200 columns, 20099 non-zeros Scaling... A: min|aij| = 1.000e+00 max|aij| = 1.607e+60 ratio = 1.607e+60 ... Constructing ...

Only top voted, non community-wiki answers of a minimum length are eligible