A linear programming reformulation of the standard quadratic optimization problem

• Main Authors: Klerk, Etienne de., Pasechnik, Dmitrii V.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2013
• Subjects: DRNTU::Science::Mathematics
• Online Access: https://hdl.handle.net/10356/94850; http://hdl.handle.net/10220/9276
• Institution: Nanyang Technological University

The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO). It is NP-hard, and contains the maximum stable set problem in graphs as a special case. In this note, we show that the SQO problem may be reformulated as an (exponen...