A note on the exact partition polytope of Frieze and Teng
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910257950752768 |
|---|---|
| author | Narayanan, Krishna Stephen, Tamon |
| author_facet | Narayanan, Krishna Stephen, Tamon |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_26505 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A note on the exact partition polytope of Frieze and Teng Narayanan, Krishna Stephen, Tamon Combinatorics Discrete Mathematics 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. |
| title | A note on the exact partition polytope of Frieze and Teng |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2605.26505 |