Polyhedral Characteristics of Balanced and Unbalanced Bipartite Subgraph Problems by Vladimir Bondarenko, Andrei Nikolaev, Dzhambolet Shovgenov

“…All three problems are established to be NP-hard. We study the polytopes and the cone decompositions of these problems and their 1-skeletons. …”
Get full text

Set-Valued Shadow Matching Using Zonotopes for 3D-Map-Aided GNSS Localization by Sriramya Bhamidipati, Shreyas Kousik, Grace Gao

“…ZSM represents buildings and GNSS shadows using constrained zonotopes, a convex polytope representation that enables propagating set-valued estimates using fast vector concatenation operations. …”
Get full text

On the Irrationality of Being in Two Minds by Shahram Dehdashti, Lauren Fell, Peter Bruza

“…We found that (1) irrational decision making necessarily involves a wider spectrum of causal relationships than rational decision making, (2) the accessible information turns out to be greater in irrational decision making when compared to rational decision making, and (3) irrational decision making is quantum-like because it violates the Bell−Wigner polytope.…”
Get full text

Specht modules and Schubert varieties for general diagrams by Liu, Ricky Ini

Get full text

Smallest Compact Formulation for the Permutahedron by Goemans, Michel X.

“…We show how to obtain an extended formulation for this polytope from any sorting network. By using the optimal Ajtai–Komlós–Szemerédi sorting network, this extended formulation has Θ(nlogn) variables and inequalities. …”
Get full text
Get full text

On the decidability of reachability in linear time-invariant systems by Fijalkow, N, Ouaknine, J, Pouly, A, Sousa-Pinto, J, Worrell, J

“…Our main contribution is to show decidability of a version of the reachability problem in which control sets are convex polytopes, under certain spectral assumptions on the transition matrix.…”

Estimating the probability that a given vector is in the convex hull of a random sample by Hayakawa, S, Lyons, T, Oberhauser, H

“…Another application is the determination of the canonical convex body included in a random convex polytope given by independent copies of X, where our combinatorial approach allows us to generalize existing results in random matrix community significantly.…”

Constrained quadratic stabilization of discrete-time uncertain nonlinear multi-model systems using piecewise affine state-feedback by Olav Slupphaug, Bjarne A. Foss

“…In different non-overlapping regions of the state-space called clusters the plant is assumed to be an element in a polytope which vertices (local models) are affine systems. …”
Get full text

Entanglement polygon inequality in qubit systems by Xiao-Feng Qian, Miguel A Alonso, J H Eberly

“…The restrictions and sharing properties associated with the inequalities are further analyzed with a geometric polytope approach, and examples of three-qubit GHZ-class and W-class entangled states are presented to illustrate the results.…”
Get full text

Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph by Alexander V. Korostil, Andrei V. Nikolaev

“…We present two backtracking algorithms for verifying vertex non-adjacency in the 1-skeleton of the traveling salesperson polytope and constructing a Hamiltonian decomposition: an algorithm based on a simple path extension and an algorithm based on the chain edge fixing procedure. …”
Get full text

THE EXTENDED NEIGHBORHOOD: DEFINITION AND CHARACTERIZATION by Orlin, James, Sharma, Dushyant

“…This result on extended neighborhoods relies on a proof that the convex hull of solutions for the graph partition problem has a diameter of 1, that is, every two corner points of this polytope are adjacent. dushyant@umich.edu…”
Get full text

Capacitated Trees, Capacitated Routing, and Associated Polyhedra by Araque, Jésus Rafael, Hall, Leslie A., Magnanti, Thomas L.

“…Our development highlights the relationship between the capacitated tree and capacitated forest polytopes and a so-called path-partitioning polytope,and shows how to use monotone polytopes and a set of simple exchange arguments to prove that valid inequalities are facets.…”
Get full text

On the Chvátal–Gomory closure of a compact convex set by Dadush, Daniel, Dey, Santanu S., Vielma, Juan Pablo

“…In this paper, we show that the Chvátal–Gomory closure of any compact convex set is a rational polytope. This resolves an open question of Schrijver (Ann Discret Math 9:291–296, 1980) for irrational polytopes, and generalizes the same result for the case of rational polytopes (Schrijver in Ann Discret Math 9:291–296, 1980), rational ellipsoids (Dey and Vielma in IPCO XIV, Lecture Notes in Computer Science, vol 6080. …”
Get full text
Get full text

The Semialgebraic Orbit Problem by Almagor, S, Ouaknine, J, Worrell, J

“…On the other hand, previous work has shown that in dimension d=4, giving a decision procedure for the special case of the Orbit Problem with singleton source set S and polytope target set T would entail major breakthroughs in Diophantine approximation.…”

Alexander and Thurston norms, and the Bieri–Neumann–Strebel invariants for free-by-cyclic groups by Funke, F, Kielak, D

“…We also prove that the Newton polytopes of the universal L2–torsion of a descending HNN extension of F2 locally determine the Bieri–Neumann–Strebel invariant of the group. …”

On the decision boundaries of neural networks: a tropical geometry perspective by Alfarra, M, Bibi, A, Hammoud, H, Gaafar, M, Ghanem, B

“…Our main finding is that the decision boundaries are a subset of a tropical hypersurface, which is intimately related to a polytope formed by the convex hull of two zonotopes. …”

Non-archimedean tame topology and stably dominated types by Hrushovski, E, Loeser, F

“…</p> <p>Beyond the foundations, the main theorem constructs a deformation retraction from the full non-archimedean space of an algebraic variety to a rational polytope. This generalizes previous results of V. Berkovich, who used resolution of singularities methods.…”

Extension Complexity, MSO Logic, and Treewidth by Petr Kolman, Martin Koutecký, Hans Raj Tiwary

“…Furthermore, we study our main geometric tool which we term the glued product of polytopes. While the glued product of polytopes has been known since the '90s, we are the first to show that it preserves decomposability and boundedness of treewidth of the constraint matrix. …”
Get full text

Comparing elliptic and toric hypersurface Calabi-Yau threefolds at large Hodge numbers by Yu-Chien Huang, Washington Taylor

“…There is a close correspondence between the structure of “tops” in the toric polytope construction and Tate form tunings of Weierstrass models for elliptic fibrations. …”
Get full text

Success and failure of attempts to improve the accuracy of Raviart–Thomas mixed finite elements in curved domains by Vitoriano Ruas

“…It is generally acknowledged that the normal component of the flux variable should preferably not take up corresponding prescribed values at nodes shifted to the boundary of the approximating polytope in the underlying normal direction. This is because an accuracy downgrade is to be expected, as shown in Bertrand and Starke (2016). …”
Get full text