A note on the exact partition polytope of Frieze and Teng
For researchers using Frieze-Teng's formulation for complexity proofs, this corrects a technical error without affecting the main results.
The authors disprove Frieze and Teng's 1994 claim that the LP-relaxation of their Exact Partition formulation is always non-degenerate, by constructing degenerate instances. They show these degeneracies can be avoided with a simple preprocessing step, preserving the complexity results.
In 1994, Frieze and Teng proposed an integer linear programming formulation of the NP-Complete Exact Partition problem, whose LP-relaxation they claimed was non-degenerate. Contrary to their claim, we show how an instance of Exact Partition can produce a degenerate polytope, and study conditions for which this can happen. We then give details of one of the smallest such degenerate Frieze-Teng polytopes, along with a closely related non-degenerate Frieze-Teng polytope that encodes an equivalent problem. We note that for the purposes of the complexity results in the literature that use their formulation, these degenerate polytopes can be avoided via a simple preprocessing step.