K. Yamanaka, D. Avis, T. Horiyama, Yoshio Okamoto, R.
Uehara and T. Yamauchi, "Algorithmic Enumeration of Surrounding
Polygons", Discrete Appl. Math 303,
305-313 (2021) pdf
D. Avis and H. Tiwary, "On
the H-free Extension Complexity of the TSP", Optimization
Letters 11(2017)445-455 arXiv:1506.08311
D. Avis and O. Friedmann, "An Exponential Lower Bound for
Cunningham's Rule"Math. Prog. B 161(2017)271-305
arXiv:1305.3944
2016
D. Avis and C. Jordan, "A Parallel Framework for Reverse
Search Using mts", arXiv:1610.07735
D. Avis and C. Meagher, "On the Directed Cut Cone and Polytope",
J. Combinatorial Optimization 31(2016)1685-1708 pdf
2015
D. Avis, "George Dantzig: father of the simplex method",
Bulletin of the EATCS 116(2015) online
D. Avis and H. Tiwary, "On the Extension Complexity of
Combinatorial Polytopes", Math.
Prog. B 153(2015)95-115 arXiv:1302.2340
D. Avis and H. Tiwary, "A Generalization of Extension
Complexity that Captures P", Information Proc. Letters
115 (2015) 6-8 , arXiv:1402.5950
D. Avis and C. Jordan, "Comparative Computational Results for
Some Vertex and Facet Enumeration Codes", arXiv:1510.02545
2014
D. Avis, D. Bremner, H. Tiwary and O. Watanabe, "Polynomial size linear programs
for non-bipartite matching problems and other problems in P",
August 2014, arXiv:1408.0807
D. Avis, K. Iwama and D. Paku, "Reputation Games for Undirected Graphs",
Discrete Applied Mathematics
166(2014)1-13 arXiv:1205.6683v1
M. Cuturi, D. Avis, "Ground Metric Learning", JMLR 15(1): 533-564 (2014) pdf
C. Meagher, R. Dimitrakopoulos and D. Avis, "Optimized Open
Pit Mine Design, Pushbacks and the Gap Problem - A Review",
Journal of Mining Science (50): 508-526 (2014). pdf
2013
D. Avis and G. Roumanis, "A
Portable Parallel Implementation of the lrs Vertex Enumeration
Code", COCOA 2013, LNCS 8287 (2013) 414-29 pdf
D. Avis and H. Tiwary, "On the Extension Complexity of
Combinatorial Polytopes", ICALP (1) 2013 57-68. arXiv:1302.2340
D. Avis, H. Miyata and S. Moriyama, "Families of Polytopal Digraphs that do not Satisfy
the Shelling Property", CGTA 46 (2013) 382-393
arXiv:1110.3078v1
2012
Y. Aoshima, D. Avis, T. Deering, Y. Matsumoto, S. Moriyama, "On the Existence of Hamiltonian
Paths for History Based Pivot Rules on Acyclic Unique Sink
Orientations of Hypercubes", Discrete Applied Mathematics, 160(15): 2104-2115 (2012), arXiv:1110.3014v2
2011
D. Avis, K. Iwama and D. Paku, "Verifying
Nash Equilibria in PageRank Games on Undirected Web Graphs",
ISAAC
2011: 415-424 pdf
2010
D. Avis,
P. Hayden and M. Wilde,
"Leggett-Garg
Inequalities
and
the
Geometry
of
the
Cut Polytope,"
Physical Review A
82, 030102(R) (2010)
arXiv:1004.3818
D. Avis, "Those ubiquitous cut
polyhedra". CCCG
2010: 25 pdf
D. Avis, "Recollections on the
Discovery of the Reverse Search Technique", LA Symposium
55(2010) 14-16 pdf
2009
D. Avis, L. Devroye and K. Iwama, "The Locker Problem with Empty
Lockers", World
Academy of Science, Engineering and Technology 60
(2009) pdf
D. Avis, S. Moriyama and M. Owari, "From Bell Inequalities to
Tsirelson's Theorem", IECIE
E92-A (2009)1254-67 pdf
D. Avis and S. Moriyama, "On
Combinatorial Properties of Linear Program Digraphs", in
Polyhedral Computation,
CRM-AMS Proceedings, 48(2009) 1-14 (Les Cahiers du Gerad,
G-2008-08) pdf
D. Avis, G. Rosenberg, R. Savani, B. von Stengel, "Enumeration of Nash Equilibria for
Two-Player Games", Economic
Theory 42(2009) 9-37 pdf
D. Avis, H. Miyata, S. Moriyama, " A Family of Polytopal Digraphs that do not Satisfy the
Shelling Property", 6-th
Japanese-Hungarian Symposium, June 2009,11 pages pdf
D. Avis and A. Broadbent, "The
Quantum Locker Puzzle", ICQNM09, Cancun,
February 2009, 4 pages. pdf
M. Ohsaki, N. Katoh, T. Kinoshita,S. Tanigawa, D. Avis
and I. Streinu,"Enumeration of Optimal
Pin
Jointed
Bistable
Compliant
Mechanisms
with
Non-Crossing
Members"
J. of Structural and
Multidisciplinary Optimization,37(2009) 645-65. pdf
2008
D. Avis, B. Kaluzny and D. Titley-Peloquin, "Visualizing and Constructing Cycles
in the Simplex Method",
Operations Research
vol 56, 512-518(2008). pdf
D. Avis, P. Hayden and I. Savov, "Distributed Compression and Multiparty Squashed
Entanglement", J. Phys.
A Math. Theor. 41, 115301, 25 pages,(2008), pdf
D. Avis, P. Fischer, A. Hilbert, A. Khrennikov, "Complete account of randomness in
the EPR-Bohm-Bell experiment", Vaxjo Conference on Foundations of Probability and
Physics-5, August 2008, 14 pages. http://arxiv.org/abs/0806.0445
D. Avis and B. Kaluzny, "Computing
Disjoint Paths on Polytopes", Journal of Combinatorial Optimization 16 (2008)
328-343. pdf
D. Avis, H. Imai and T. Ito,"Generating Facets of the Cut Polytope by Triangular
Elimination", Mathematical
Programming 112(2008)303-25. pdf
D. Avis, N. Katoh, M. Ohsaki, I. Streinu and S. Tanigawa, "Enumerating Constrained
Non-crossing Minimally Rigid Frameworks", Discrete and Computational Geometry
40 (2008) 31-46 pdf
D. Avis, P. Hayden and I. Savov, "Multiparty Distributed Compression of Quantum
Information", ICQNM08, Martinique,
February 2008, 7 pages. pdf
2007
D. Avis and T. Ito, "New Classes
of Facets of the Cut Polytope and Tightness of the I_mm22 Bell
Inequalities", Discrete
Applied Mathematics 155 (2007) 1689-99, pdf
D. Avis, "Quantum Correlations:
From Bell inequalities to Tsirelson's Theorem", Proc. International Workshop on
Combinatorics 2007, Yokohama, June 2007. pdf
D. Avis, N. Katoh, M. Ohsaki, I. Streinu and S. Tanigawa, "Enumerating Planar Minimally Rigid
Graphs", Graphs and Combinatorics 23
(2007) 117-134. pdf
D.Avis, A. Bondy, W. Cook and B. Reed, "Vasek Chvatal: A Short Introduction", Graphs and Combinatorics 23
(2007) 41-66. pdf
D. Avis and T. Ito, "Comparison
of Two Bounds of the Quantum Correlation Set", ICQNM07, Guadeloupe,
January 2007. pdf
D. Avis and T. Imamura, "A List
Heuristic for Vertex Cover", Operations Research Letters 35 (2007) 201-4.
ps
2006
D. Avis and A. Deza, "Un des
"problemes delectables" de Claude Berge", Discrete Mathematics
306(2006)2299-2302 pdf
D. Avis and T. Ito, "Polyhedral
and Semidefinite Approaches to Classical and Quantum Bell
Inequalities", AQIS
2006, Beijing, Sep 2006, 2 pages pdf
N. Katoh, M. Ohsaki, T. Kinoshita, S. Tanigawa, D. Avis and I.
Streinu, "Enumeration of Optimal
Pin-Jointed Bistable Mechanisms", 4th China-Japan-Korea Symp. of
Structural and Mechanical Systems, Kunming, Nov 2006, 6
pages. pdf
D. Avis, H. Imai and T. Ito, "On
the Relationship Between Convex Bodies Related to
Correlation Experiments with Dichotomic Observables",
Journal of Physics A 39
(2006) 11283-99, pdf
T. Ito, H. Imai and D. Avis, "Bell
Inequalities Stronger than the CHSH Inequality for Three-level
Isotropic States", Physical
Review A 73(4) (2006) 042109(9 pages)
pdf
D. Avis, J. Hasegawa, Y. Kikuchi and Y. Sasaki, " A Quantum Protocol to Win the Graph
Colouring Game on all Hadamard Graphs", Proceedings of the IEICE E89A
(2006) 1378-81. pdf
2005
D. Avis, H. Imai, T. Ito and Y. Sasaki, "Two-party Bell Inequalities Derived from Combinatorics
via Triangular Elimination", August 2005, 20 pages, Journal of Physics A 38(50)
(2005)10971-10987, pdf
D. Avis, C. De Simone, and B. Reed, "On the fractional chromatic index of
a graph and its complement", Operations Research Letters, vol 33, pp. 385-388
(2005) pdf
2004
D. Avis, H. Imai, T. Ito and Y. Sasaki, "Deriving Tight Bell Inequalities for 2 Parties with
Many 2-valued Observables from Facets of Cut Polytopes",
24 pages, April 2004. http://arxiv.org/abs/quant-ph/0404014
D. Avis and B. Kaluzny, "Solving
Inequalities and Farkas' Lemma Made Easy", AMS Mathematical Monthly, vol
111, pp 152-157(2004) ps
2003
D. Avis and J. Umemoto, "Stronger
Linear Programming Relaxations for Max -Cut", Mathematical Programming, vol.
B 97, pp. 451-469 (2003). ps
D. Avis, "On the Complexity of
Testing Hypermetric, Negative Type, k-gonal and Gap Inequalities",
Lecture Notes in Computer Science,
LNCS 2866, pp 51-59 (2003). ps
2002
D. Avis, K. Fukuda and S. Picozzi, "On Canonical Representations of Convex Polyhedra",
Mathematical Software,
ICMS 2002, Ed. A. Cohen, X-S Gao, N. Takayama, World Scientific,
pp.350-360 (2002) ps
D. Avis and V. Chvatal, "On a
Conjecture of Baiou and Balinski", DIMACS Technical Report
2002-08, March 2002. ps
D. Avis, C. De Simone, P. Nobili, "On the Chromatic Polynomial of a Graph", Mathematical Programming,
vol B 92, pp. 439-452(2002) ps
2001
D. Avis, K. Hosono, M. Urabe, "On
the Existence of a Point Subset with a Specified Number
of Interior Points," Discrete Mathematics, Vol. 241, pp. 33-40.
(2001) ps
D. Avis and A. Deza, "On the
Solitaire Cone and its Relationship to Multicommodity Flows"
Mathematical Programming,
Vol. 90, pp. 27-57 (2001). ps.
D. Avis and A. Deza, "On the
Binary Solitaire Cone", Discrete
Applied Mathematics, Vol. 115, pp. 3-14
(2001) ps
2000
D. Avis and L. Devroye, "Estimating
the
Number of Vertices of a Polyhedron," Information Processing Letters,
Vol 73, pp. 137-143. ps
D. Avis, K. Hosono, M. Urabe, "On
the Existence of a Point Subset with a 4 or 5
Interior Points,"
Lecture Notes in Computer Science, Vol. 1763, pp. 57-64
(2000) ps.
- D. Avis, S. Onn, and A. Deza, "A Combinatorial Approach to the
Solitaire Game", IEICE Trans. on Fund. of Electronics,
Communications and Computer Sciences E83-A, pp.
656-661(2000). .ps
D. Avis, "Living with
lrs," Lecture Notes
in Computer Science, Vol. 1763, pp. 47-56
(2000) ps
D. Avis, "lrs: A
Revised Implementation of the Reverse Search Vertex
Enumeration Algorithm," In: Polytopes - Combinatorics and
Computation, G. Kalai & G. Ziegler eds.,
Birkhauser-Verlag, DMV Seminar Band 29, pp. 177-198
(2000) .ps
1998
D. Avis, "Computational
Experience with the Reverse Search Vertex Enumeration
Algorithm," Optimization
Methods
and Software, Vol. 10, pp.107-124 (1998)
ps.
1997
D. Avis, D. Bremner, and R. Seidel, "How Good are Convex Hull Algorithms?," Computational Geometry: Theory
and Applications, Vol. 7, pp. 265-301 (1997). ps
1996
D. Avis and K. Fukuda, "Reverse
Search for Enumeration," Discrete Applied Math, Vol. 6, pp. 21-46 (1996). pdf
D. Avis, "Generating Rooted Triangulations Without Repetitions,"
Algorithmica, Vol. 16, pp.618-632(1996).pdf
D. Avis and Chiu Ming Kong, "Generating Rooted Triangulations with Minimum
Degree Four," Technical
Report, Vol. SOCS 96.9, McGill University, (1996). ps
T. Ono, Y. Kyoda, T. Masada, K. Hayase, T. Shibuya, M. Inaba,
H. Imai, K. Imai, and D. Avis, "A Package for Triangulations (Video)," in Proc. 12th Annual ACM Symp. on
Comput. Geom., ACM Press, Philadelphia, PA (1996). ps.
1995
D. Avis and D. Bremner, "How
Good are Convex Hull Algorithms?," pp. 20-28 in Proc. 11th Annual ACM Symp. on
Comput. Geom., (June 1995). ps
D. Avis and M. Houle, "Computational
Aspects of Helly's Theorem and its Relatives," International Journal of
Computational Geometry & Applications, Vol. 5,
pp. 357-367 (1995). ps
1994
- D. Avis and H. Maehara, "Metric
Extensions and the L1-Hierarchy," Discrete Mathematics,
Vol. 131, pp. 17-28 (1994). ps
-
D. Avis, "A C Implementation
of the Reverse Search Vertex Enumeration Algorithm," in
RIMS Kokyuroku 872, ed.
H. Imai, Kyoto University (May 1994). ps
G. Ceder, G. D. Garbulsky, D. Avis, K.
Fukuda "
Ground states of a ternary fcc lattice model with
nearest- and next-nearest-neighbor interactions",
Physical
Review B 49 (1), 1-7 (1994)
pdf
1993
- D. Avis and V. P. Grishukhin, "A Bound on the k-gonality of Facets of the
Hypermetric Cone and Related Complexity Problems," Computational Geometry: Theory
and Applications, Vol. 2, pp. 241-254 (1993). ps
- D. Avis, "The m-Core
Properly Contains the m-Divisible Points in Space," Pattern Recognition Letters,
Vol. 14, pp. 703-705 (1993). ps
1992
- D. Avis and K. Fukuda, "A
Pivoting Algorithm for Convex Hulls and Vertex Enumeration
of Arrangements and Polyhedra," Discrete and Computational
Geometry, Vol. 8, pp. 295-313 (1992).ps
1991
- D. Avis and M. Deza, "The
Cut Cone, L1-Embedability, Complexity and Multicommodity
Flows," Networks,
Vol. 21, pp. 595-617 (1991). ps
- D. Avis, P. Erdos, and J. Pach, "Distinct Distances Determined by a Subset of Points
in Space," Computational
Geometry: Theory and Applications, Vol. 1, pp. 1-12
(1991). ps
- D. Avis and K. Fukuda, "A Basis Enumeration Algorithm for Linear Systems with Geometric Applications
in Space," Applied
Math. Letters, Vol. 4, pp. 39-42
(1991). ps
1990
- D. Avis, "On the
Complexity of Isometric Embedding in the Hypercube,"
Proc. SIGAL Int. Symp. on
Algorithms, pp. 348-357 Springer-Verlag, (1990). ps
- D. Avis and M. Doskas, "Algorithms
for High Dimensional Stabbing Problems," Discrete Applied Math.,
Vol. 27, pp. 39-48 (1990). ps
1989
- D. Avis and Mutt, "All
the Facets of The Six Point Hamming Cone," European Journal of Combinatorics,
Vol. 10, pp. 309-312 (1989). ps
- D. Avis, J-M. Robert, and R. Wenger, "Lower Bounds for Line Stabbing,"
Information Processing
Letters, Vol. 33, pp. 59-62 (1989). ps
1988
D. Avis, P. Erdos, and J. Pach, "Repeated
Distances in Space," Graphs
and Combinatorics, Vol. 4, pp. 207-217 (1988). ps
D. Avis, B. K. Bhattacharya, and H. Imai、"Computing the Volume of the Union of Spheres", The Visual Computer, (1988)
3:323-328 pdf
- D. Avis and C. W. Lai, "The
Probabilistic
Analysis of a Heuristic for the Assignment Problem,"
SIAM Journal on Computing,
Vol. 17, pp. 732-741(1988).ps
1987
- D. Avis and R. Wenger, "Algorithms
for Line Transversals in Space," Proceedings of the 3rd ACM
Conference on Computational Geometry, pp. 300-307
(1987). ps
- D. Avis and H. ElGindy, "Triangulating
Point Sets in Space,"
Discrete and Computational Geometry, Vol. 2, pp.
99-111 (1987). ps
- D. Avis, "Space
Partitioning and its Application to Generalized Retrieval
Problems," pp. 237-249 in Foundations of Data Organization, ed.
S.Ghosh, Y. Kambayashi, K. Tanaka, Plenum Press (1987). ps
1986
D. Avis, "Diameter Partitioning,"
Discrete and Computational
Geometry, Vol. 1, pp. 265-276 (1986). ps
1985
D. Avis and D. Rappaport, "Computing
the
Largest Empty Convex Subset of a Set of Points" Proc. 1st ACM Symposium on
Computational Geometry, pp. 161-167, 1985.pdf
D. Avis, "On the
Partitionability Point Sets in Space" Proc. 1st ACM Symposium on
Computational Geometry, pp. 116-120, 1985.pdf
D. Avis, "Non-partitionable point sets", Information
Processing Letters Vol. 19 Issue 3, Oct. 1984 pp 125 -
129 pdf
1981
D. Avis, "Hypermetric Spaces and
the Hamming Cone," Can.
J. Math, Vol 33, pp 795-802, 1981. pdf
1980
D. Avis, “Lower Bounds for
Geometric Problems,” 18th
Allerton Conference, pp. 35-40, Urbana, IL (1980). pdf
D. Avis, "A Note on Some
Computationally Difficult Set Covering Problems, " Mathematical Programming 18
(1980) 138-145. pdf
D. Avis, "On the Extreme
Rays of the Metric Cone," Can. J. Math, Vol 32, pp 126-144, 1980. pdf
D. Avis and M. Newborn, "On Pop Stacks in Series," Utilitas
Mathematica Vol 19, pp129-40 pdf
D. Avis, "Comments on a Lower Bound for Convex Hull Determination,"
Inf. Process. Lett., Vol 11, pp.126, 1980 pdf
1979
D. Avis, "On Minimal 5-Chromatic Triangle-Free Graphs,"
J. Graph Theory, Vol 79, pp.397-400, 1979 pdf
D. McCallum and D. Avis, "A Linear Algorithm for Finding the Convex Hull of a Simple Polygon,"
Inf. Process. Lett., Vol 9, pp.201-6, 1979 pdf
1978
D. Avis and V. Chvatal, "Notes on Bland's Pivoting Rule,"
Math Prog. Study, Vol 8, pp.24-34, 1978 pdf