Publications On-line              (For a complete publication list see CV )

2023

D. Avis and D. A. Hoang,  "A Note On Acyclic Token Sliding Reconfiguration Graphs of Independent Sets ",  arXiv:2301.00317

D. Avis and S. Hernández-Cuenca, "On the foundations and extremal structure of the holographic entropy cone", Discrete Applied Mathematics 328, 16-39 (2023)  arXiv:2102.07535
 

2022

D. Avis and D. A. Hoang,  "On Reconfiguration Graph of Independent Sets under Token Sliding", Graphs and Combinatorics (to appear) arXiv:2203.16861

2021

D. Avis and D. Bremner, (tSparktope: linear programs from algorithms", Optimization and Software Methods  36:2-3, 279-300 (2021) arXiv:2005.02853

D. Avis and C. Jordan, "lrsarith: a small fixed/hybrid arithmetic C library",  arXiv:2101.12425

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

2020

D. Avis and  L. Devroye, "An Analysis of Budgeted Parallel Search on Conditional Galton-Watson Trees", Algorithmica 82(5): 1329-1345 (2020) arXiv:1703.10731

2019

D. Avis, D. Bremner, H. Raj Tiwary, O. Watanabe, "Polynomial size linear programs for problems in P."  Discrete Appl. Math. 265: 22-39 (2019) arXiv:1408.0807

D. Avis and H. Tiwary, "Compact Linear Programs for 2SAT", Eur. J. Comb. 80: 17-22 (2019)    arXiv:1702.06723

D. Avis and C. Jordan,  "mts: A light framework for parallelizing tree search codes",Optimization and Software Methods (online)   arXiv:1709.07605

2018

D. Avis and C. Jordan, "mplrs: A Scalable Parallel Vertex/Facet enumeration Code", Math. Prog. Computation  10(2018)267-302  arXiv:1511.06487

2017

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 () 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 (),     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

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