OLD PAPERS

Here you can find an old collection of some papers in older versions. I do not maintain the latest there anymore.

Some of my old papers in ALGEBRAIC OPTIMIZATION/COMPUTATION

  • The paper surveys several techniques to exactly count or estimate the number of lattice points inside a bounded polyhedral region in space.

  • In the paper Computation in Multicriteria Matroid Optimization Using recent work on algorithmic theory for nonlinear and multicriteria matroid optimization, we have developed algorithms and heuristics aimed at practical solution of large instances of some of these difficult problems. Our methods primarily use the local adjacency structure inherent in matroid polytopes to pivot to feasible solutions which may or may not be optimal. We also present a modified breadth-first-search heuristic that uses adjacency to enumerate a subset of feasible solutions. We present other heuristics, and provide computational evidence supporting our techniques. We implemented all of our algorithms in the software package MOCHA.

  • In the paper How to integration a polynomial over a simplex We did a thorough investigation of how to do exact integration of a polynomial over a simplex and more generally, convex polyhedral regions. Will appear in Mathematics of Computation.

  • The paper Computing Infeasibility Certificates for combinatorial problems through Hilbert's Nullstellensatz continues our development of the Nullstellensatz Linear Algebra algorithm (NulLA) from both a computational and a theoretical perspective. From the computational perspective, we compare computations over the rationals to computations over finite fields; we discuss mathematical ideas for optimizing NulLA ranging from the algebraic to the probabilistic (e.g., using symmetries), and we report on experiments proving the non-$3$-colorability of graphs with almost two thousand vertices and tens of thousands of edges. A shorter version appeared in the proceedings of ISSAC 2008. It does not contain all the results of the full version.

  • In a paper recently submitted to IPCO 2010 , we have improved NulLA (both in theory and practice), by creating a variation of the Border bases algorithm, called FPNulLA. We discuss the performance of NulLA and FPNulLA (much better than NulLA). We use these two algorithms, as well as Gr\"obner bases and the Theta bodies of Gouveia, Parrilo and Thomas, for the recognition of combinatorial properties such as $k$-colorability, unique Hamiltonicity, and automorphism rigidity of graphs. We report on computational complexity bounds, structural results.

  • The paper Computation with Polynomial Equations and Inequalities arising in Combinatorial Optimization is a survey of the use of algebraic techniques in combinatorial optimization. The techniques we discuss here use the algebra of multivariate polynomials with coefficients over a field to create large-scale linear algebra or semidefinite programming relaxations of many kinds of feasibility or optimization questions.

  • The paper Pareto Optima of Multicriteria Integer Linear Programs proves a generalization of Lenstra's theorem for integer programming in fixed dimension. In this case, a multiobjective integer linear optimization problem with fixed number of variables and a fixed number of objective functions can be solved in polynomial time. This paper appeared in INFORMS journal of Computing.

  • The paper Integer polynomial optimization in fixed dimension settles the computational complexity of this kind of integer programs and then gives an FPTAS for the problem of finding approximations to the maximization of a polynomial over the lattice points of a polyhedron. A ground breaking result in non-linear integer programming. It appeared in Mathematics of Operations Research

  • Also accepted in Mathematical Programming is our follow up paper on the the mixed-integer case for the same problem above.

  • Test sets are important tools in Algebraic Optimization. Recently we wrote two papers on a nice situation when the computation of Graver bases can be efficiently done and optimization can also be carried on efficiently: First, to appear in the journal Discrete Optimization is a prove that n-fold integer linear programs can be solved efficiently. There is a follow-up paper to appear in the Journal of Pure and Applied Algebra where we deal with convex objective maximization problems n-fold convex maximization

  • The paper All Linear and Integer Programs are Slim 3-way Transportation Programs (joint with S. Onn) presents a polynomial time algorithm that encodes ANY convex rationalpolyhedron as a 3-way transportation polytope. This means that3-way transportation polytopes are as nasty as any general polytope.This has consequences in Discrete Optimization and Statistics. The software implementing this algorithm is available here too. This paper appeared in SIAM journal of Optimization

    OLD papers in COMBINATORICS

  • The paper Ehrhart polynomials of matroids and polymatroids (joint with D. Haws and M. Koeppe) shows a curious family of polytopes whose dimension grows yet we can efficiently compute their Ehrhart polynomials (we dont know many of them).

  • The paper On the computation of Clebsch-Gordan coefficients and the dilation effect (joint with T.B. McAllister) we investigate the problem of computing tensor product multiplicities for complex semisimple Lie algebras. Remarkable new conjectures generalizing the saturation theorem are proposed (the dilation effect). Download software from Tyrrell's web page.

  • The paper The many aspects of counting lattice points in polytopes is a survey of the applications, theory and algorithms for the problem in the title.

  • The paper Effective Lattice Point Counting in Rational Convex Polytopes (joint with R. Hemmecke, J. Tauzer and R. Yoshida) presents the software LATTE the first full implementation of Barvinok's algorithm. The paper discusses our tricks to implement it, a ``polar'' variation that runs faster in practice, and presents LOTS of concrete calculations and applications (e.g explicit Ehrhart quasipolynomials). For more information on LattE, please see LattE's home page

  • Here is an example, in MAPLE, of our formula for the volume of the Birkhoff polytope $B_3$.

  • The paper Algebraic Unimodular Counting (joint with B. Sturmfels) This was the great-grand father of the LATTE project. The paper presents several computational results regarding counting unimodular vector partition functions, in particular the problem of counting Contingency tables and Kostant's partition function of the root system A_n.
  • You can also play online with Kostant's partition function and download software for counting contingency table here