LOCATION: Freie Universität Berlin, Department of Computer Science, main lecture hall, Takustraße 9, 14195 Berlin (→ directions)
| Program | |
|---|---|
| 13:45–14:15 | coffee and tea |
| 14:15–15:15 | MAIN LECTURE Anusch Taraz (TU München): Embedding spanning graphs into dense and sparse graphs |
| 15:15–15:45 | tea and coffee |
| 15:45–16:15 | Jannik Matuschke (TU Berlin): Lattices and maximum flow algorithms in planar graphs |
| 16:15–16:45 | Claudia Dieckmann (FU Berlin): Finding a regular polygon in a set of disks |
| 16:45–17:00 | coffee and tea |
| 17:00–17:30 | Timo Berthold (ZIB Berlin) UNDERCOVER - a primal heuristic for MINLP based on sub-MIPs generated by set covering |
| 17:30–18:00 | Antonios Antoniadis (HU Berlin): Approximability of Edge Matching, Jigsaw Puzzles and Polyomino Matching |
| 18:00 | Closing words and wrap-up session |
| 18:05 | BAT-Fest in the courtyard |
In this talk we will discuss the following scenario: we are given two graphs G and H, and our aim is to find a copy of H in a graph G' derived from G by an evil adversary who has deleted some edges in G.
If G is the complete graph on n vertices, and H is a graph of fixed order and chromatic number r, then the classical theorem of Erdös and Stone asserts that the adversary can roughly delete any 1/(r-1) portion of the edges and we can still find a copy of H in G'.
However, we are interested in sparse graphs G and spanning subgraphs H, and will head towards the following result: If G is a random graph on n vertices with an appropriate, vanishing edge probability, and H is an r-chromatic n-vertex graph with bounded expansion and bounded maximum degree, then with high probability we can allow the adversary to roughly delete any 1/r-portion of the edges incident at every vertex of G and still find a copy of H in G'.
This is joint work with J. Böttcher and Y. Kohayakawa.
Given an unordered set of n disks, we ask if we can choose a point from each disk such that the selected points form a regular n-gon.
We present a polynomial-time algorithm for this problem and explain how it can also be used to find a regular n-gon in a set of lines, squares, elipses etc.
This is joint work with Lena Schlipf.
We present Undercover, a primal heuristic for mixed-integer nonlinear programming (MINLP). The heuristic constructs a mixed-integer linear subproblem (sub-MIP) of a given MINLP by fixing a subset of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed in order to linearize each constraint. Subsequently, these variables are fixed to approximate values, e.g., obtained from a linear outer approximation. The resulting sub-MIP is solved by a mixed-integer linear programming solver. Each feasible solution of the sub- MIP corresponds to a feasible solution of the original problem.
Although general in nature, the heuristic seems most promising for mixed-integer quadratically constrained programs (MIQCPs). We present computational results on a general test set of MIQCPs selected from the MINLPLib.
We study the (in)approximability of Edge Matching Puzzles. The interest in Edge Matching Puzzles has been raised in the last few years with the release of the "Eternity II" puzzle, with a $2 million prize for the first submitted correct solution. It is known that it is NP-hard to solve these puzzles exactly. We extend on that result by showing an approximation-preserving reduction from Max-3DM-B and thus proving that Edge Matching Puzzles do not admit polynomial-time approximation schemes unless P=NP. We then show that the problem is APX-complete and prove lower and upper bounds on its approximation factor. Finally, we extend our (in)approximability results to several other related types of puzzles.