solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看3354次
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. (arXiv:1708.02222v2 [cs.DS] UPDATED)
来源于:arXiv
We derandomize the famous Isolation Lemma by Mulmuley, Vazirani, and Vazirani
for polytopes given by totally unimodular constraints. That is, we construct a
weight assignment such that one vertex in such a polytope is isolated, i.e.,
there is a unique minimum weight vertex. Our weights are quasi-polynomially
bounded and can be constructed in quasi-polynomial time. In fact, our isolation
technique works even under the weaker assumption that every face of the
polytope lies in an affine space defined by a totally unimodular matrix. This
generalizes the recent derandomization results for bipartite perfect matching
and matroid intersection.
We prove our result by associating a lattice to each face of the polytope and
showing that if there is a totally unimodular kernel matrix for this lattice,
then the number of near-shortest vectors in it is polynomially bounded. The
proof of this latter geometric fact is combinatorial and follows from a
polynomial bound on the number of near-shortest circ 查看全文>>