Zobrazeno 1 - 10
of 244
pro vyhledávání: '"Avis, David"'
Autor:
Avis, David
Every polyhedron can be described by an H-representation H(P) consisting of half spaces or equivalently by a V-representation V(P) as the convex hull of a set of vertices and extreme rays. By a suitable encoding we can define a polyhedron Q by settin
Externí odkaz:
http://arxiv.org/abs/2406.03698
Autor:
Avis, David, Jordan, Charles
We describe a parallel implementation in lrslib for removing redundant halfspaces and finding a minimum representation for an H-representation of a convex polyhedron. By a standard transformation, the same code works for V-representations. We use thi
Externí odkaz:
http://arxiv.org/abs/2406.00065
Autor:
Avis, David, Hoang, Duc A.
Publikováno v:
Ars Combinatoria 159:133-154, 2024
We continue the study of token sliding reconfiguration graphs of independent sets initiated by the authors in an earlier paper (arXiv:2203.16861). Two of the topics in that paper were to study which graphs $G$ are token sliding graphs and which prope
Externí odkaz:
http://arxiv.org/abs/2301.00317
Autor:
Avis, David, Hoang, Duc A.
Publikováno v:
Graphs and Combinatorics: Vol. 39: Iss. 3, Article 59 (2023)
An independent set of a graph $G$ is a vertex subset $I$ such that there is no edge joining any two vertices in $I$. Imagine that a token is placed on each vertex of an independent set of $G$. The $\mathsf{TS}$- ($\mathsf{TS}_k$-) reconfiguration gra
Externí odkaz:
http://arxiv.org/abs/2203.16861
Autor:
Avis, David, Hernández-Cuenca, Sergio
Publikováno v:
Discret. Appl. Math. 328 (2023) 16
The holographic entropy cone (HEC) is a polyhedral cone first introduced in the study of a class of quantum entropy inequalities. It admits a graph-theoretic description in terms of minimum cuts in weighted graphs, a characterization which naturally
Externí odkaz:
http://arxiv.org/abs/2102.07535
Autor:
Avis, David, Jordan, Charles
We describe lrsarith which is a small fixed precision and hybrid arithmetic C library for integers and rationals that we developed for use in the lrslib library for polyhedral computation. Using a generic set of operations, a program can be compiled
Externí odkaz:
http://arxiv.org/abs/2101.12425
Autor:
Avis, David, Bremner, David
In a recent paper Avis, Bremner, Tiwary and Watanabe gave a method for constructing linear programs (LPs) based on algorithms written in a simple programming language called Sparks. If an algorithm produces the solution $x$ to a problem in polynomial
Externí odkaz:
http://arxiv.org/abs/2005.02853
Autor:
Avis, David, Hernández-Cuenca, Sergio
Publikováno v:
In Discrete Applied Mathematics 31 March 2023 328:16-39
Autor:
Avis, David, Jordan, Charles
We describe mts, a generic framework for parallelizing certain types of tree search programs including reverse search, backtracking, branch and bound and satisfiability testing. It abstracts and generalizes the ideas used in parallelizing lrs, a reve
Externí odkaz:
http://arxiv.org/abs/1709.07605
Autor:
Avis, David, Devroye, Luc
Recently Avis and Jordan have demonstrated the efficiency of a simple technique called budgeting for the parallelization of a number of tree search algorithms. The idea is to limit the amount of work that a processor performs before it terminates its
Externí odkaz:
http://arxiv.org/abs/1703.10731