Francqui Chair (ULg 2011-2012): Yurii Nesterov (UCL)

Complexity and Simplicity of Optimization Problems

Workshop schedule

  • 9h-9h30: Coffee and welcome

  • 9h30-10h15: Etienne de Klerk

    Improved lower bounds on crossing numbers of graphs through optimization


    The crossing number problem for graphs is to draw (or embed) a graph in the plane with a minimum number of edge crossings. Crossing numbers are of interest for graph visualization, VLSI design, quantum dot cellular automata, RNA folding, and other applications. On the other hand, the problem is notoriously difficult. In 1973, Erdös and Guy wrote that: "Almost all questions that one can ask about crossing numbers remain unsolved." For example, the crossing numbers of complete and complete bipartite graphs are still unknown. The case of the complete bipartite graph is known as Turán's brickyard problem, and was already posed by Paul Turán in the 1940's. Moreover, even for cubic graphs, it is NP-hard to compute the crossing number.

    Different types of crossing numbers may be defined by restricting drawings; thus the two-page crossing number corresponds to drawings where all vertices are drawn or a circle, and all edges either inside or outside the circle. It is conjectured that the two-page and normal crossing numbers coincide for complete and complete bipartite graphs. In this talk, we will survey some recent results, where improved lower bounds were obtained for (two-page) crossing numbers of complete and complete bipartite graphs through the use of optimization techniques.

    (Joint work with D.V. Pasechnik)


  • 10h15-10h45: Coffee break

  • 10h45-11h30: Alexandre d'Aspremont

    Semidefinite Programming on a Shoestring


    We discuss a low rank, very economical, stochastic regularization result for maximum eigenvalue minimization. We then study the complexity of an optimal stochastic minimization algorithm on this problem.

    This is joint work with Noureddine El Karoui at U.C. Berkeley.


  • 11h30-12h15: Michel Baes

    Minimizing convex functions over integer points


    We consider the problem of minimizing a Lipschitz-continuous and strongly convex functions over integer points in a polytope. We assume that we have at our disposal a black-box algorithm that solves some special quadratic integer problems with a constant approximation factor. Based on this black-box procedure, we design and study an iterative procedure to solve our original problem. Despite the generality of the underlying problem, we prove that we can find efficiently, with respect to our assumptions regarding the encoding of the problem, a feasible solution whose objective function value is close to the optimal value. We describe a few situations where we can implement the needed black-box procedure efficiently.

    (Joint work with Alberto Del Pia, Yurii Nesterov, Shmuel Onn, Christian Wagner, and Robert Weismantel)