Research and Publications
My research is in convex, and integer programming. A few subjects that I especially like are listed below.
Convex Programming
I have developed a theory on the ``Facial Structure of Conic Linear Programs'', which
generalizes the known theory on facial structure, basic solutions,
nondegeneracy, and strict complementarity in linear programming.
Many known results on the geometry of convex programs fit into this framework as special cases,
and some new ones can be derived from it. See the paper
and
a talk .
I gave a new, surprisingly simple condition for a classical problem in convex analysis: the closedness of the linear image of a closed
convex cone.
See the
paper. This result implies that all "badly behaved
semidefinite programs look the same". The paper is forthcoming; in the meantime, see the talks
.
Integer Programming
On a reformulation technique for general integer programs that makes
many hard instances easy, see a talk ,
and a
paper .
Applications of Optimization
With coauthors Burcu Aydin, Haonan Wang, Liz Bullitt, and Steve Marron, we developed a methodology to compute principal components in trees.
A mention of this work in the journal La Recherche.
With this work, student Burcu Aydin won the interactive session at the INFORMS annual meeting in Fall 2008 in Washington DC
Publications
Convex Programming
- Computational Semidefinite Programming and Related Optimization
Problems: The State of the Art, Mathematical Programming Series B, Vol 95, No. 2 (2003) G. Pataki, Guest Editor
- A Simple Derivation of a Facial Reduction Algorithm, and
Extended Dual Systems, G. Pataki submitted
-
On the Closedness of the Linear Image of a Closed Convex Cone , G. Pataki,
Mathematics of Operations Research. Vol 32 (2), 395-412
- The Geometry of Cone-LP's, G. Pataki,
in H. Wolkowicz, L. Vandenberghe and R. Saigal, ed.: The Handbook of Semidefinite Programming, Kluwer, 2000
- On the Generic Properties of Convex Optimization Problems in
Conic Form, G. Pataki and L. Tuncel Mathematical Programming A 89 (2001) 449-457
- On the Rank of Extreme Matrices in Semidefinite Programs and the
Multiplicity of Optimal Eigenvalues, G. Pataki Mathematics of Operations Research, 23 (2), 339-358, 1998
- Cone-LP's and Semidefinite Programs: Geometry and
a Simplex-type Method, G. Pataki in Proceedings of the Fifth IPCO Conference, Springer-Verlag 1996
Integer Programming
- Basis Reduction, and the Complexity of Branch-and-Bound, G. Pataki, Mustafa Tural, Erick B. Wong,
to appear, 2010 Symposium on Discrete Algorithms (SODA)
- Branching proofs of infeasibility in low density subset sum problems, G. Pataki and Mustafa Tural, submitted
- Unifying LLL inequalities G. Pataki and Mustafa Tural, submitted
- Parallel Approximation and Integer Programming Reformulation, G. Pataki and M. Tural,
submitted
- LLL Reduction, and the Parallel Approximation Problem, G. Pataki and M. Tural,
in the proceedings of the
LLL+25 conference
Note: the results of this paper are subsumed by, and contained in the above 3 papers.
- Column Basis Reduction and Decomposable Knapsack Problems, B. Krishnamoorthy and G. Pataki,
Discrete Optimization, 6(3), August 2009, 242-270
- Teaching Integer Programming Formulations Using the Traveling Salesman Problem, G. Pataki
SIAM Review, Vol 45, No. 1 (2003), 116-123
- OCTANE: A New Heuristic for Pure 0-1 Programs, E. Balas, S. Ceria, M. Dawande, G. Pataki and F. Margot
Operations Research 49 (2001), 207-235
- Solving Integer and Disjunctive Programs by Lift-and-Project, S. Ceria and G. Pataki
in Proceedings of the Sixth IPCO Conference, 1998
- Solving the seymour problem, M. C. Ferris, G. Pataki and S. Schmieta
Optima, 66:1-7, 2001.
- Polyhedral Methods for the Maximum Clique Problem, E. Balas, S. Ceria, G. Cornuejols and G. Pataki
in Proceedings of the Second DIMACS Challenge, 1996
Applications of Optimization
- A Principal Component Analysis for Trees B. Aydin, G. Pataki, H. Wang, E. Bullitt, and S. Marron, Accepted at Annals of Applied Statistics
- Schlumberger Optimizes Receiver Location for Automated Meter
Reading, L. Clarke, S. Gavirneni and G. Pataki Interfaces, Vol 34, No.3 (2004), 208-214
Some Talks: