Extended Formulations for Polygons

Extended Formulations for Polygons

The extension complexity of a polytope P is the smallest integer k such that P is the projection of a polytope Q with k facets. We study the extension complexity of n-gons in the plane. First, we give a new proof that the extension complexity of regular n-gons is O(log n), a result originating from...

Volledige beschrijving

Bibliografische gegevens
Hoofdauteurs:	Fiorini, Samuel, Tiwary, Hans Raj, Rothvoss, Thomas
Andere auteurs:	Massachusetts Institute of Technology. Department of Mathematics
Formaat:	Artikel
Taal:	English
Gepubliceerd in:	Springer-Verlag 2017
Online toegang:	http://hdl.handle.net/1721.1/107947

Gelijkaardige items

Some 0/1 polytopes need exponential size extended formulations
door: Rothvoss, Thomas
Gepubliceerd in: (2016)

Circumscribing Polygons and Polygonizations for Disjoint Line Segments
door: Akitaya, Hugo A., et al.
Gepubliceerd in: (2022)

POLYGONS AND GRAVITONS
door: Hitchin, N
Gepubliceerd in: (1979)

On k-convex polygons
door: Aichholzer, Oswin, et al.
Gepubliceerd in: (2014)

Minimality and mutation-equivalence of polygons
door: Prince, T, et al.
Gepubliceerd in: (2017)

Polygonal instabilities on interfacial vorticities
door: Labousse, M., et al.
Gepubliceerd in: (2016)

Computing Signed Permutations of Polygon
door: Aloupis, Greg, et al.
Gepubliceerd in: (2012)

On the optimal bisection of a polygon
door: Koutsoupias, E, et al.
Gepubliceerd in: (2015)

On the optimal bisection of a polygon
door: Koutsoupias, E, et al.
Gepubliceerd in: (2015)

Equivariant Semidefinite Lifts of Regular Polygons
door: Fawzi, Hamza, et al.
Gepubliceerd in: (2021)

Discrete Equidecomposability and Ehrhart Theory of Polygons
door: Turner, Paxton, et al.
Gepubliceerd in: (2021)

Equivariant Semidefinite Lifts of Regular Polygons
door: Fawzi, Hamza, et al.
Gepubliceerd in: (2019)

The propagation and growth of polygonal fault systems
door: King, J
Gepubliceerd in: (2021)

Salt polygons and porous media convection
door: Lasser, J, et al.
Gepubliceerd in: (2023)

SIMD column-parallel polygon rendering
door: Eldridge, Matthew Willard
Gepubliceerd in: (2007)

Percolation on self-dual polygon configurations
door: Bollobas, B, et al.
Gepubliceerd in: (2010)

Polygonal model for layered inorganic nanotubes
door: Tibbetts, Kevin, et al.
Gepubliceerd in: (2010)

On polygonal measures with vanishing harmonic moments
door: Pasechnik, D, et al.
Gepubliceerd in: (2014)

On the inverse spectral problem for polygonal domains
door: Durso, Catherine
Gepubliceerd in: (2014)

Extended Formulations in Mixed-Integer Convex Programming
door: Yamangil, Emre, et al.
Gepubliceerd in: (2019)

Anisotropic imbibition on surfaces patterned with polygonal posts.
door: Blow, M, et al.
Gepubliceerd in: (2011)

Detecting and improving feature lines on polygonal meshes
door: Toni.
Gepubliceerd in: (2013)

Numerical modelling of the growth of polygonal fault systems
door: King, JJ, et al.
Gepubliceerd in: (2022)

Any Monotone Function Is Realized by Interlocked Polygons
door: Demaine, Erik D., et al.
Gepubliceerd in: (2014)

Extended formulations in mixed integer conic quadratic programming
door: Dunning, Iain Robert, et al.
Gepubliceerd in: (2018)

Chromatic equivalence classes of certain generalized polygon trees
door: Peng, Yee Hock, et al.
Gepubliceerd in: (1997)

Pencirian pokok poligon = (A characterization of polygon tree).
door: Peng, Yee-Hock
Gepubliceerd in: (1990)

Single Polygon Counting on Cayley Tree of Order 3
door: Pah, Chin Hee
Gepubliceerd in: (2010)

Snipperclips: Cutting tools into desired polygons using themselves
door: Abel, Zachary, et al.
Gepubliceerd in: (2022)

Internal friction and absence of dilatancy of packings of frictionless polygons
door: Radjai, Franck, et al.
Gepubliceerd in: (2015)

Shape simplification through polygonal approximation in the fourier domain
door: Andrews, Mark, et al.
Gepubliceerd in: (2015)

Ultra-slow throw rates of polygonal fault systems
door: King, JJ, et al.
Gepubliceerd in: (2020)

Intersection Graphs of Maximal Sub-polygons of k-Lizards
door: Daugherty, Caroline, et al.
Gepubliceerd in: (2023)

Area-Optimal Simple Polygonalizations: The CG Challenge 2019
door: Demaine, Erik, et al.
Gepubliceerd in: (2022)

Rectilinear polygon partitioning for region coverage using UAVs
door: Amit Agarwal
Gepubliceerd in: (2010)

View-dependent feature line detection on polygonal meshes
door: Yang, Jingcan
Gepubliceerd in: (2015)

An operator product expansion for polygonal null Wilson loops
door: Alday, L, et al.
Gepubliceerd in: (2011)

Stochastic processes that generate polygonal and related random fields
Gepubliceerd in: (2003)

Making polygons by simple folds and one straight cut
door: Demaine, Erik D., et al.
Gepubliceerd in: (2012)

An operator product expansion for polygonal null Wilson loops
door: Alday, L, et al.
Gepubliceerd in: (2011)