Skip to main navigation Skip to search Skip to main content

On modelling hard combinatorial optimisation problems as linear programs: Refutations of the 'unconditional impossibility' claims

  • University of Connecticut
  • SUNY Buffalo

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

There has been a series of developments in the recent literature (by essentially a same 'circle' of authors) with the absolute/unconditioned (implicit or explicit) claim that there exists no abstraction of an NP-complete combinatorial optimisation problem in which the defining combinatorial configurations [such as 'tours' in the case of the travelling salesman problem (TSP) for example] can be modelled by a polynomial-sized system of linear constraints. The purpose of this paper is to provide general as well as specific refutations for these recent claims.

Original languageEnglish
Pages (from-to)261-278
Number of pages18
JournalInternational Journal of Operational Research
Volume40
Issue number2
DOIs
StatePublished - 2021

Keywords

  • Combinatorial optimisation
  • Computational complexity
  • Linear programming
  • P vs. NP
  • Travelling salesman problem
  • TSP

Fingerprint

Dive into the research topics of 'On modelling hard combinatorial optimisation problems as linear programs: Refutations of the 'unconditional impossibility' claims'. Together they form a unique fingerprint.

Cite this