Complete enumeration of small realizable oriented matroids.
Technical report, 2010.
submitted to CCCG (Canadian Conference on Computational Geometry) 2010.
The Holt-Klee condition for oriented matroids.
Europ. J. Combinatorics, 30(8):1854-1867, 2009.
http://www.arxiv.org/abs/math.CO/0612073.
Every non-Euclidean oriented matroid admits a biquadratic final polynomial.
Combinatorica, 29(6):691-698, 2009.
http://www.arxiv.org/abs/math.CO/0510500.
Combinatorial characterizations of K-matrices.
http://arxiv.org/abs/0911.2171, 2009.
Pivoting in linear complementarity: two polynomial-time cases.
Discrete Comput. Geom., 42:187-205, 2009.
http://arxiv.org/abs/0807.1249.
An output-sensitive algorithm for multi-parametric lcps with sufficient matrices.
In D. Avis, D. Bremner, and A. Deza, editors, Polyhedral Computation, volume 48 of CRM Proceedings and Lecture Notes, pages 73-102. Amer. Math. Soc., Providence, RI, 2009.
http://arxiv.org/abs/0807.2318.
Multiple-symbol differential detection based on combinatorial geometry.
IEEE Transactions on Communications, 56(10):1596-1600, 2008.
A linear equation for minkowski sums of polytopes relatively in general position.
Europ. J. Combinatorics, to appear, 2008.
http://arxiv.org/abs/0712.0027.
Facet computation for minkowski sums of polytopes.
Technical report, Swiss Federal Institute of Technology, Switzerland, 2008.
Three pathological rank-
oriented matroids.
Technical report, 2008.
Multiple-symbol differential detection based on combinatorial geometry.
In Proceedings of the IEEE International Conference on Communications (ICC 2007), Glasgow, United Kingdom, pages 827-832, 2007.
Realizations of oriented matroids by polynomial optimization.
Technical report, 2007.
submitted.
-vectors of Minkowski additions of convex polytopes.
Discrete Comput. Geom., 37:503-516, 2007.
http://www.springerlink.com/content/r552751m4081506l/.
A conjecture about Minkowski additions of convex polytopes.
In Proceedings of the 23rd European Workshop on Computational Geometry, pages 54-56, 2007.
Polynomial time algorithms for maximizing the intersection volume of polytopes.
Pacific Journal of Optimization, 3:37-52, 2007.
The generic Gröbner walk.
J. Symbolic Computation, 42:298-312, 2007.
Electronic version in http://www.elsevier.com/wps/find/journal_browse.cws_hom e.
Computing Gröbner fans.
Mathematics of Computation, 76:2189-2212, 2007.
Electronic version available from http://www.ams.org/mcom/.
New polynomial-time algorithms for Camion bases.
Discrete Mathematics, 306:3302-3306, 2006.
http://www.sciencedirect.com/science/journal/.
Primal-dual algorithms for data depth.
In Regina Y. Liu, editor, Data Depth: Robust Multivariate Analysis, Computational Geometry and Applications, volume 72 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, pages 171-194. AMS, 2006.
Computing all faces of the Minkowski sum of
-polytopes.
In Proceedings of the 17th Canadian Conference on Computational Geometry, 2005.
http://cccg.cs.uwindsor.ca/copy.htm.
New polynomial-time algorithms for Camion bases.
preprint, EPFL, Switzerland, July 2005.
submitted to Discrete Mathematics.
Comparing the strengths of non-realizability certificates for oriented matroids, 2005.
presented at the 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Application.
Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm.
European Journal of Operational Research, 166:35-50, 2005.
http://authors.elsevier.com/sd/article/S0377221704003352.
A case when the union of polytopes is convex.
Linear Algebra and its Applications, 397:381-388, 2005.
ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports/convuni041108.pdf.
Exact parallel algorithms for the location depth and the maximum feasible subsystem problems.
In C.A. Floudas and P. M. Pardalos, editors, Frontiers in global optimization, volume 74 of Nonconvex Optim. Appl., pages 123-133. Kluwer Acad. Publ., Boston, MA, 2004.
The criss-cross method can take
pivots.
In Proc. 20th Annu. ACM Sympos. Comput. Geom., pages 401-408. ACM Press, New York, 2004.
http://www.acm.org/dl/.
From the zonotope construction to the Minkowski addition of convex polytopes.
Journal of Symbolic Computation, 38(4):1261-1272, 2004.
pdf file available from http://www.cs.mcgill.ca/~fukuda/download/paper/minksum031007jsc.pdf.
Primal-dual algorithms for data depth.
Technical report, ETH Zurich, 2004.
ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports/primaldual040920_TR.pdf.
Optimal tolerancing in mechanical design using polyhedral computation tools, 2003.
presented at 19th European Workshop of Computational Geometry, March 24-26, Bonn.
An adaptive algorithm for vector partitioning.
Journal of Global Optimization, 25:305-319, 2003.
http://www.cs.mcgill.ca/~fukuda/download/paper/aavp011105.ps.gz.
Combinatorial generation of small point configurations and hyperplane arrangements.
In B. Aronov and J. Pach, editors, The Goodman-Pollack Festschrift, pages 425-440. Springer-Verlag, 2003.
http://www.cs.mcgill.ca/~fukuda/download/paper/cgspc020924.pdf.
On the face lattice of the metric polytope.
In J. Akiyama, M. Kano, and M. Urabe, editors, Lecture Notes in Computer Science. Springer-Verlag, 2003.
Generation of oriented matroids - a graph theoretical approach.
Discrete Comput. Geom., 27:117-136, 2002.
ps file available from ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports/GenerationOfOMs001031.ps.gz.
Notes on acyclic orientations and the shelling lemma.
Theoretical Computer Science, 263:9-16, 2001.
ps file available from ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports/acyclic980112.ps.gz.
Extended convex hull.
Computational Geometry, 20:13-23, 2001.
http://www.sciencedirect.com/science/journal/09257721.
Towards a unified framework for randomized pivoting algorithms in linear programming.
In P. Kall and H.-J. Lüthi, editors, Operations Research Proceedings 1998, pages 113-122, 1999.
ps file available from ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports/randsimp9810.ps.gz.
EP theorems and linear complementarity problems.
Discrete Applied Mathematics, 84:107-119, 1998.
Criss-cross methods: A fresh view on pivot algorithms.
Mathematical Programming, 79:369-395, 1997.
The existence of a short sequence of admissible pivots to an optimal basis in LP and LCP.
Int. Trans. Opl. Res., 4:273-284, 1997.
Double description method revisited.
In M. Deza, R. Euler, and I. Manoussakis, editors, Combinatorics and Computer Science, volume 1120 of Lecture Notes in Computer Science, pages 91-111. Springer-Verlag, 1996.
ps file available from ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports/ddrev960315.ps.gz.
On extremal behaviors of Murty's least index method.
Mathematical Programming, 64:365-370, 1994.
Antipodal graphs and oriented matroids.
Discrete Mathematics, 111:245-256, 1993.
Linear complementarity and oriented matroids.
Journal of the Operations Research Society of Japan, 35:45-61, 1992.
A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra.
Discrete Comput. Geom., 8:295-313, 1992.
Oriented matroid programming.
Ph.D. thesis, Univ. of Waterloo, Waterloo, Canada, 1982.
ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports/fukuda1982thesis.pdf.