Research and Publications
My research is in the area of convex, especially semidefinite, 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 .
Publications
For some published papers, only the final submitted version is
provided, due to copyright restrictions.
If a paper is "in preparation", but there is a link to the file, then
it hasn't been submitted yet, but
it is in a readable, and referenceable form.
Convex Programming
- Computational Semidefinite Programming and Related Optimization
Problems: The State of the Art,
G. Pataki, Guest Editor
Mathematical Programming Series B, Vol 95, No. 2 (2003)
Link
on Springer's website
- A Simple Derivation of a Facial Reduction Algorithm, and
Extended Dual Systems,
G. Pataki
in preparation. ps pdf
- On the Closedness of the Linear Image
of a Closed Convex Cone.
G. Pataki
Math. Oper. Res. Vol 32 (2), 395-412 ps pdf
- The Geometry of Cone-LP's,
G. Pataki
in H. Wolkowicz, L. Vandenberghe and R. Saigal, ed.:
The Handbook of Semidefinite Programming, Kluwer, 2000 ps
pdf
- On the Generic Properties of Convex Optimization Problems in
Conic Form
G. Pataki and L. Tuncel
Mathematical Programming A 89 (2001) 449-457 ps
pdf
- On the Rank of Extreme Matrices in Semidefinite Programs and the
Multiplicity of Optimal Eigenvalues,
G. Pataki
Mathematics of Operations Research, 23 (2), pg. 339-358, 1998
ps pdf
- Cone-LP's and Semidefinite Programs: Geometry and
a Simplex-type Method
G. Pataki
in Proceedings of the Fifth IPCO Conference, Springer-Verlag
1996 ps pdf
Integer Programming
- Branching proofs of infeasibility in low density subset sum problems
G. Pataki and Mustafa Tural, submitted
- Sublattice determinants in reduced bases
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, submitted
- Teaching Integer Programming Formulations Using the Traveling
Salesman Problem
G. Pataki
SIAM Review, Vol 45, No. 1 (2003), 116-123 pdf
- 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 pdf
- Solving Integer and Disjunctive Programs by Lift-and-Project
S. Ceria and G. Pataki
in Proceedings of the Sixth IPCO Conference, 1998 ps
pdf
- Solving the seymour problem (nonrefereed)
M. C. Ferris, G. Pataki and S. Schmieta
Optima, 66:1-7, 2001. pdf
- Polyhedral Methods for the Maximum Clique Problem
E. Balas, S. Ceria, G. Cornuejols and G. Pataki
in Proceedings of the Second DIMACS Challenge, 1996
Other subjects
- Schlumberger Optimizes Receiver Location for Automated Meter
Reading
L. Clarke, S. Gavirneni and G. Pataki
Interfaces, Vol 34, No.3 (2004), 208-214 pdf
Some Talks: