Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with regular lattice:
TR17-127 | 12th August 2017
Rohit Gurjar, Thomas Thierauf, Nisheeth Vishnoi

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Revisions: 1

We deterministically construct quasi-polynomial weights in quasi-polynomial time, such that in a given polytope with totally unimodular constraints, one vertex is isolated, i.e., there is a unique minimum weight vertex.
More precisely,
the property that we need is that every face of the polytope lies in an affine space defined ... more >>>

ISSN 1433-8092 | Imprint