Publications
On-line
(For a
complete publication list see CV )
2013
D. Avis and H. Tiwary, "On the Extension Complexity of
Combinatorial Polytopes", (abstract in ICALP 2013) arXiv:1302.2340
D. Avis and O. Friedmann, "An Exponential Lower Bound for
Cunningham's Rule", arXiv:1305.3944
2012
D. Avis, K. Iwama and D. Paku, "Reputation Games for Undirected
Graphs", May 2012, arXiv:1205.6683v1
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, online June 20,
2012, arXiv:1110.3014v2
D. Avis, H. Miyata and S. Moriyama, "Families of Polytopal Digraphs that do not Satisfy the
Shelling Property", Oct. 2011, arXiv:1110.3078v1
(To appear, CGTA 46 (2013)
382-393, online Nov. 11, 2012)
2011
M. Cuturi, D. Avis, "Ground Metric Learning", arXiv:1110.2306v1
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,"
arXiv:1004.3818 Physical Review A 82,
030102(R) (2010)
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
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
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
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
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
1978
D. Avis and V. Chvatal, "Notes on Bland's Pivoting Rule,"
Math Prog. Study, Vol 8, pp.24-34, 1978 pdf
- .
- .