hrcak mascot   Srce   HID

Croatian Operational Research Review, Vol. 5 No. 2, 2014.

Izvorni znanstveni članak
https://doi.org/10.17535/crorr.2014.0001

From combinatorial optimization to real algebraic geometry and back

Janez Povh ; Faculty of Information Studies Novo Mesto

Puni tekst: engleski, pdf (113 KB) str. 105-117 preuzimanja: 587* citiraj
APA 6th Edition
Povh, J. (2014). From combinatorial optimization to real algebraic geometry and back. Croatian Operational Research Review, 5 (2), 105-117. https://doi.org/10.17535/crorr.2014.0001
MLA 8th Edition
Povh, Janez. "From combinatorial optimization to real algebraic geometry and back." Croatian Operational Research Review, vol. 5, br. 2, 2014, str. 105-117. https://doi.org/10.17535/crorr.2014.0001. Citirano 25.01.2021.
Chicago 17th Edition
Povh, Janez. "From combinatorial optimization to real algebraic geometry and back." Croatian Operational Research Review 5, br. 2 (2014): 105-117. https://doi.org/10.17535/crorr.2014.0001
Harvard
Povh, J. (2014). 'From combinatorial optimization to real algebraic geometry and back', Croatian Operational Research Review, 5(2), str. 105-117. https://doi.org/10.17535/crorr.2014.0001
Vancouver
Povh J. From combinatorial optimization to real algebraic geometry and back. Croatian Operational Research Review [Internet]. 2014 [pristupljeno 25.01.2021.];5(2):105-117. https://doi.org/10.17535/crorr.2014.0001
IEEE
J. Povh, "From combinatorial optimization to real algebraic geometry and back", Croatian Operational Research Review, vol.5, br. 2, str. 105-117, 2014. [Online]. https://doi.org/10.17535/crorr.2014.0001

Sažetak
In this paper, we explain the relations between combinatorial optimization and real algebraic geometry with a special focus to the quadratic assignment problem. We demonstrate how to write a quadratic optimization problem over discrete feasible set as a linear optimization problem over the cone of completely positive matrices. The latter formulation enables a hierarchy of approximations which rely on results from polynomial optimization, a sub- eld of real algebraic geometry.

Ključne riječi
combinatorial optimization; copositive programming; semide nite programming; polynomial optimization; sum of squares; real algebraic geometry

Hrčak ID: 133615

URI
https://hrcak.srce.hr/133615

Posjeta: 888 *