Invited Session Fri.3.H 2038

Friday, 15:15 - 16:45 h, Room: H 2038

Cluster 4: Conic programming [...]

Algebraic symmetry in semidefinite programming


Chair: Etienne de Klerk



Friday, 15:15 - 15:40 h, Room: H 2038, Talk 1

Etienne de Klerk
Improved lower bounds on crossing numbers of graphs via semidefinite programming

Coauthor: Dmitrii V. Pasechnik


The crossing number problem for graphs is to draw 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 in general. 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. 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 via optimization.



Friday, 15:45 - 16:10 h, Room: H 2038, Talk 2

Marianna Eisenberg-Nagy
Symmetry in RLT cuts for the quadratic assignment and standard quadratic optimization problems

Coauthors: Etienne De Klerk, Renata Sotirov, Uwe Truetsch


The reformulation-linearization technique (RLT), introduced in [W.,P. Adams, H.,D. Sherali, A tight linearization and an algorithm for zero-one quadratic programming problems, Management Science, 32(10): 1274-1290, 1986], provides a way to compute linear programming bounds on the optimal values of NP-hard combinatorial optimization problems. This type of method has become known as a lift-and-project strategy: the "lifting'' refers to the addition of new variables, and the "projection'' to projecting the optimal values of the new variables to a feasible point of the original problem.
We study the RLT technique for two specific problems, namely the standard quadratic program and the quadratic assignment problem (QAP). We show how one may solve the second level RLT relaxation with additional semidefinite programming constraints in the presence of suitable algebraic symmetry in the problem data. As a result we are able to compute the best known bounds for certain graph partitioning problems involving strongly regular graphs. These graph partitioning problems have QAP reformulations.



Friday, 16:15 - 16:40 h, Room: H 2038, Talk 3

Dion Gijswijt
Symmetric semidefinite programs based on tuples


The independence number in graphs can be bounded using semidefinite programming. Symmetries of the graph can be used to reduce the size of the SDP. A dramatic example of this occurs in coding theory, where the Lovász theta number for exponentially large graphs reduces to a polynomial sized LP (Delsarte bound) by virtue of the large symmetry group of the Hamming space.
Here we discuss stronger bounds, related to the Lasserre hierarchy, that involve tuples of vertices of the graph. We show efficient methods to apply symmetry reduction in this case. An explicit result (joint work with A. Schrijver and H. Mittelmann) gives improved bounds on binary codes using four-tuples, and shows that the quadruply shortened Golay code is optimal.


  USA Payday Loans Online. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.