Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/44072
Title: | Approximate cone factorizations and lifts of polytopes | Authors: | Gouveia, João Parrilo, Pablo A. Thomas, Rekha R. |
Issue Date: | 2015 | Publisher: | Springer | Project: | info:eu-repo/grantAgreement/FCT/COMPETE/132981/PT | Serial title, monograph or event: | Mathematical Programming | Volume: | 151 | Issue: | 2 | Abstract: | In this paper we show how to construct inner and outer convex approximations of a polytope from an approximate cone factorization of its slack matrix. This provides a robust generalization of the famous result of Yannakakis that polyhedral lifts of a polytope are controlled by (exact) nonnegative factorizations of its slack matrix. Our approximations behave well under polarity and have efficient representations using second order cones. We establish a direct relationship between the quality of the factorization and the quality of the approximations, and our results extend to generalized slack matrices that arise from a polytope contained in a polyhedron. | URI: | https://hdl.handle.net/10316/44072 | DOI: | 10.1007/s10107-014-0848-z 10.1007/s10107-014-0848-z |
Rights: | embargoedAccess |
Appears in Collections: | I&D CMUC - Artigos em Revistas Internacionais |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
GPTfinal.pdf | 662.72 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
4
checked on Mar 25, 2024
WEB OF SCIENCETM
Citations
10
3
checked on May 2, 2023
Page view(s) 20
745
checked on Mar 26, 2024
Download(s)
198
checked on Mar 26, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.