Publications
On-line
(For a complete
publication list see CV )
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)
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). ps.
D. Avis, "Generating Rooted Triangulations Without Repetitions,"
Algorithmica, Vol. 16, pp.618-632(1996).ps.
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. Vol. 1, pp. 265-276 (1986).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 programs, " Mathematical Programming 18 (1980)
138-145. pdf
- .
- .