DIMACS Workshop on Algorithmic Challenges in Optimization, Game Theory and Computer Science: in Memory of Leo Khachiyan

March 9 - 10, 2009
DIMACS Center, CoRE Building, Rutgers University

Endre Boros, Director of RUTCOR, Endre.Boros at rutcor.rutgers.edu
Vladimir Gurvich, RUTCOR, gurvich at rutcor.rutgers.edu


Selin Damla Ahipasaoglu, Cornell University and Michael J. Todd

Title: A Modified Frank-Wolfe Algorithm for Computing Minimum-Area Enclosing Ellipsoidal Cylinders: Theory and Algorithms

Given an arbitrary set in the Euclidean space, we are interested in finding an ellipsoidal cylinder, centered at the origin, such that its intersection with a certain subspace has minimum area. This problem is referred to as the Minimum-Area Enclosing Ellipsoidal Cylinder (MAEC) problem. We show that MAEC and its dual can be written as convex problems, and present a Frank-Wolfe type algorithm with away steps. We discuss global and local convergence properties of the algorithm and present some computational results.

Miguel F. Anjos, University of Nottingham

Title: Recent progress in the application of semidefinite programming to discrete optimization

The celebrated max-cut algorithm of Goemans and Williamson is 15 years old in 2009, and its impact in the area of semidefinite programming has been remarkable. In this talk, we will survey some of the most recent developments in the application of semidefinite programming to discrete optimization problems. We will also highlight promising directions for research in this area.

Alexander Engau, Waterloo University

Title: HIPCUT - A hybrid interior-point cutting-plane method for integer Programming

To solve the continuous relaxations of discrete optimization problems, we integrate a cutting-plane scheme into the general framework of an infeasible interior-point algorithm. Instead of adding cuts only after finding approximate solutions to successive relaxations, separating inequalities are also added and removed already during the solution process based on feasibility indicators at intermediate iterates. Preliminary computational results are reported for instances of the max-cut problem.

Nir Halman, Massachusetts Institute of Technology

Title: Strongly subexponential algorithms for Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games

We show that a Simple Stochastic Game (SSG) can be formulated as an LP-type problem. Using this formulation, and the known algorithm of Sharir and Welzl for LP-type problems, we obtain the first strongly subexponential solution for SSGs.

Using known reductions between various games, we achieve the first strongly subexponential solutions for Discounted Payoff Games and Mean Payoff Games. We also give alternative simple proofs for the best known upper bounds for Parity Games and binary SSGs.

Bahman Kalantari, Rutgers University

Title: Matrix scaling in linear and convex programming

Diagonal scaling in linear programming became a prominent technique with the announcement of Karmarkar algorithm. In the context of nonnegative matrices, doubly stochastic diagonal scaling had been a subject of research for more than half a century prior to the emergence of interior-point methods for LP. The link between these two otherwise disjoint fields is diagonal scaling of a symmetric positive semidefinite matrix into a doubly quasi-stochastic matrix. The complexity of the latter problem was studied by Khachiyan and Kalantari who also used it to give, as a by-product, a simple unique path-following algorithm for LP. In this talk not only do we wish to promote and justify the significance and relevance of positive semidefinite matrix scaling in linear programming, but of its generalization in semidefinite as well as self-concordant programming. These are from the point of view of pedagogical, foundational, theoretical, algorithmic, and possibly even practical considerations.

Kaz Makino, University of Tokyo

Title: Computational Aspects of Monotone Dualization

Dualization of a monotone Boolean function represented by a conjunctive normal form (CNF) is a problem which, in different disguise, is ubiquitous in many areas including Computer Science, Artificial Intelligence, and Game Theory to mention some of them. It is also one of the few problems whose precise tractability status (in terms of polynomial-time solvability) is still unknown, and now open for more than 25 years. We briefly survey computational results for this problem, where we focus on the famous paper by Fredman and Khachiyan (J.~Algorithms, 21:618--628, 1996), which showed that the problem is solvable in quasi-polynomial time (and thus most likely not \coNP-hard), as well as on follow-up works.

Arkadi Nemirovski, Georgia Institute of Technology

Title: Acceleration by randomization: randomized first order algorithms for large-scale convex optimization

In 1995, Grigoriadis and Khachiyan proposed the very first sublinear time randomized algorithm for matrix games. In the talk, we discuss recent explanation, extensions and modifications of this surprising result and outline their potential applications in large-scale Signal Processing and Semidefinite Programming.

Uriel G. Rothblum, The Technion and Arkadi Nemirovski and Shmuel Onn

Title: Accuracy certificates for computational problems with convex structure

The goal of the current paper is to introduce the notion of certificates which verify the accuracy of solutions of computational problems with convex structure; such problems include minimizing convex functions, variational inequalities with monotone operators, computing saddle points of convex-concave functions and solving convex Nash equilibrium problems. We demonstrate how the implementation of the Ellipsoid method and other cutting plane algorithms can be augmented with the computation of such certificates without essential increase of the computational effort. Further, we show that (computable) certificates exist whenever an algorithm is { capable} to produce solutions of guaranteed accuracy.

Andrzej Ruszczynski, Rutgers University

Title: Computational Challenges in Risk-Averse Optimization

Modern risk averse optimization models involve objective and constraint functions which are compositions of convex non-smooth mappings and smooth functions. We shall present ways of dealing with them in an efficient way by primal and dual methods, and we shall discuss computational challenges in multistage problems. The talk will be illustrated by a portfolio optimization problem.

Mario Szegedy, Rutgers University

Title: Product rules in Semidefinite Programming

In recent years we witness the proliferation of semidefinite programming bounds in combinatorial optimization, quantum computing, and even in complexity theory. In these bounds the key observation is often the fact that the new parameter in question is multiplicative with respect to the product of the problem instances. Our goal is to classify those semidefinite programming instances for which the optimum is multiplicative under a naturally defined product operation. The product operation we define generalizes the ones used in Shannon capacity paper of L. Lovasz and XOR game paper of R. Cleve, W. Slofstra, F. Unger and S. Upadhyay. We find conditions under which the product rule always holds and give examples for cases when the product rule does not hold.

(Joint with Rajat Mittal and Troy Lee)

Sergei Tarasov and Misha Vyalyi, Dorodnitsyn Computing Center, Moscow

Title: Could exact SDP be a computationally hard problem?

We conjecture that the Exact Semidefinite Programming Problem (ESDP): to check whether some affine subspace of square matrices with rational entries intersects the cone of positive semidefinite matrices, could be intrinsically difficult contrary to the intuiton that the problem is convex and some of its approximate versions are effectively solvable.

Specifically we show how to reduce to ESDP the well-known problem of comparing numbers represented by arithmetic circuits. The last problem is considered to be difficult and from algorithmic viewpoint is equivalent according to Allender E. et al (2005) to the generic task of numerical computation. Thus the comparison problem lowerbounds ESDP. The result essentially uses the exact duality theory for SDP obtained earlier by Ramana M. (1997). We plan to discuss related matters and, in particular, whether it is possible to use some different mathematical programming problems in order to simulate the comparison problem.

Tamás Terlaky, Lehigh Unviersity

Title: Three decades of polynomial time algorithms for LP

In 1972 the Klee-Minty example made explicit that well known variants of the simplex algorithm are not polynomial time algorithms. The quest for polynomial time algorithms for LP started, and Khachiyan's gave the first polynomial time algorithm for LP in1979. Khachiyan's elipsoid method was not only a polynomial time algorithm for LP, but combined with column (constraint) generation schemes, it also allowed to design polynomial time algorithms for large classes of combinatorial optimization problems. Although ellipsoid methods did not yield computationally efficient algorithms for solving large scale practical problems, and since 1984 interior point methods (IPMs) enjoyed better complexity for general LP's, the ellipsoid method remained the only polynomial time algorithm for solving LP's with either exponentially many variables, or exponentially many constraints on the dual side. Only volumetric center cutting plane IPMs could provide better complexity for such problems. Now, after three decades there is a rich library of polynomial time algorithms; implementations methodology and software went through revolutionary improvements; polynomial time algorithms were extended to large classes of comnvex optimization problems; we understand the limitations of Ellipsoid methods and IPMs. The next challenges include the design of a strongly polynomial time algorithm for LP, and to develop scalable parallel algorithms that utilize the growing number of available processors.

Misha Vyalyi, Dorodnitsyn Computing Center, Moscow

Title: On complexity of algorithmic linear algebra problems in exponential dimension

Is it easy to check that Ax=0? The answer depends on data specification. The problem becomes nontrivial when dimensions of the matrix A and the vector x are exponential w.r.t. the input size.

In the talk we present several versions of this problem and discuss their computational complexity. We show that one of them has applications in algorithmic number theory.

Complexity of feasibility problem for linear equation systems will also be discussed in these `exponential dimension' settings.

(joint work with Qi Cheng, S. Tarasov)

Neal Young, University of California - Riverside

Title: Beating simplex for fractional packing and covering linear programs

We describe an approximation algorithm for packing and covering linear programs (linear programs with non-negative coefficients). Given a constraint matrix with n non-zeros, r rows, and c columns, the algorithm (with high probability) computes feasible primal and dual solutions whose costs are within a factor of 1+epsilon of the optimal cost in time O( n + (r+c)log(n)/epsilon^2 ).

For dense problems (with r,c=O(sqrt(n))) this time is O(n +sqrt(n)log(n)/epsilon^2) --- linear even as epsilon tends to zero. In comparison, previous Lagrangian-relaxation algorithms generally take at least Omega(n log(n)/epsilon^2) time, while (for small epsilon) the Simplex algorithm typically takes at least Omega(n min(r,c)) time.

This extends a previous algorithm by Grigoriadis and Khachiyan for approximately solving 2-player zero-sum games in sub-linear time.

(joint work with Christos Koufogiannakis)

Previous: Program
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on February 17, 2009.