Combinatorial Geometry and Optimization

This is a joint seminar of the Discrete Optimization Group, the Combinatorial Geometry Group and the Theory of Computation Lab.

 

Calendar

May 11, 2012, 16:15h – MA B1 524

Dömötör Pálvölgyi, ELTE, “Covering points with boxes and domination in transitive colorings of tournaments“

Given two points $p,q\in \R^d$, define $box(p,q)$ as the smallest closed box whose edges are parallel to the axes and contains $p$ and $q$.Denote by $g(d)$ the smallest number such that we can select $g(d)$ points, $T$, from any finite collection of points, $S\subset\R^d$, such that for any point $s\in S$ we have two points, $p,q\in T$ for which $s\in box(p,q)$.We prove that $g(d)\le O(d\log d 2^{2^{d-1}})$ improving on earlier bounds by B\’ar\’any and Lehel, Pach, Alon et al. We also improve the best bound known in $3$-dimensions from $3^{14}$ to $64$ and propose possible further improvements through finding the maximum domination number over parity tournaments.

An edge coloring of a tournament $T$ with colors $1,2,\dots,k$ is called \it $k$-transitive \rm if the digraph $T(i)$ defined by theedges of color $i$ is transitively oriented for each $1\le i \le k$. We explore the following conjecture of Gy\’arf\’as (which is a weakening of a conjecture of Erd\H os) and show how it is related to the box cover problem.

Conjecture: For each positive integer $k$ there exists a (least) $p(k)$ such that every $k$-transitive tournament has a dominating set of at most $p(k)$ vertices.

Joint work with András Gyárfás.

 

March 27, 2012, 14:15 – MA B1 524

Gabriel Nivasch, EPFL  “The union-find algorithm, path compressions, and the inverse Ackermann function“

We will explain the relation between the union-find algorithm and path compressions, and we will prove the famous quasilinear inverse-Ackermann upper bound on its running time. We will follow the “top-down analysis” of Seidel and Sharir (2005).

February 24, 2012, 14:15 – MA B1 524

Géza Tóth, Rényi Institute, Budapest,  “Monotone crossing number“

The monotone crossing number of $G$ is defined as the smallest number of crossing points in a drawing of $G$ in the plane, where every edge is represented by an $x$-monotone curve, that is, by a connected continuous arc with the property that every vertical line intersects it in at most one point. It is shown that this parameter can be strictly larger than the classical crossing number $cr(G)$, but it is bounded from above by $cr^2(G)$. This is in sharp contrast with the behavior of the rectilinear crossing number, which cannot be bounded from above by any function of $cr(G)$.

Joint work with Janos Pach.

 

February 23, 2012, 14:15h – MA B1 524

Andrew Suk, MIT,  “Coloring intersection graphs of x-monotone curves in the plane“

A class of graphs G is \chi-bounded if the chromatic number of the graphs in G is bounded by some function of their clique number. We show that the class of intersection graphs of simple x-monotone curves in the plane intersecting a vertical line is \chi-bounded. As a corollary, the class of intersection graphs of rays in the plane is \chi-bounded.

 

December 20, 2011, 15:15h – MA B1 524

Gabriel Nivasch, EPFL,  “Upper bounds for centerflats“

For every fixed d and every n, we construct an n-point set G in R^d such that every line in R^d is contained in a halfspace that contains only 2n/(d+2) points of G (up to lower-order terms). Apparently, the point set G satisfies the following more general property: For every k, every k-flat in R^d is contained in a halfspace that contains only (k+1) n / (d+k+1) points of G (up to lower-order terms).

In 2008, Bukh, Matousek, and Nivasch conjectured the following generalization of Rado’s centerpoint theorem: For every n-point set S in R^d and every k, there exists a k-flat f in R^d such that every halfspace that contains f contains at least (k+1) n / (d+k+1) points of S (up to lower-order terms). (The centerpoint theorem is obtained by setting k=0.) Such a flat f would be called a “centerflat”. Thus, our upper bound construction shows that the leading constant (k+1)/(k+d+1) in the above conjecture is tight (certainly for k = 1, and apparently for all k). The set G of our construction is the “stretched grid” — a point set which has been previously used by Bukh et al. for other related purposes.

Joint work with Boris Bukh.

 

December 20, 2011, 14:00h – MA B1 524

Andreas Holmsen, KAIST,  “Order-types of families of convex sets”

I will define the order-type of a family of convex sets, which captures certain convexity properties of families of convex sets in the plane. Our notion of an order-type has many nice properties and applications:

• The order-type naturally extends the notion of the order-type for points in the plane and, more generally, acyclic oriented matroids. In particular every acyclic oriented matroid of rank 3 has a realization by convex sets.
• The realization space of a given order-type is a contractible set.
• The Erdos-Szekeres theorem holds for families of convex sets: Any family of non-crossing convex sets in general position contains a large subfamily in convex position. In particular, the problem for convex sets is equivalent to the problem for acyclic oriented matroids.

             The talk is based on joint work with Michael Dobbins and Alfredo Hubard.

 

December 15, 2011, 14:00h – MA B1 524

József Solymosi, UBC, Vancouver,  “Bounds on point-line incidences”

A central result in discrete geometry is the Szemeredi-Trotter theorem which gives a sharp bound on the number of point-line incidences in the Euclidean plane. The result has various generalizations and applications. In this talk we state an extension of the Szemeredi-Trotter theorem and we show some new applications. For example, using incidence bounds, we show that if M is an n-element set of k x k matrices with real coefficients such that det(A – B) is not zero for any distinct A,B elements of M and V,W are n-element sets of k dimensional vectors, then |V +W| + |MW| >> n^{5/4}.
Joint work with Terry Tao.

November 8, 2011, 14:00h – MA B1 524

Géza Tóth, Rényi Institute, Budapest, “Degenerate thrackles”

A thrackle is a graph drawn in the plane such that any two edges have exactly one common point, which is either a common vertex, or a crossing. According to Conway’s famous conjecture, a thrackle of $n$ vertices has at most $n$ edges. This conjecture is still open, in spite of many efforts. Here we investigate two variants. A {\em tangle} is a graph drawn in the plane such that any two edges have exactly one common point, which is either a common vertex, or a {\em touching point}. We verify the analogue of Conway’s conjecture that is, we show that a tangle of $n$ vertices has at most $n$ edges and this bound is sharp. A {\em tangled thrackle} combination of the thrackle and the tangle, it is a graph drawn in the plane such that any two edges have exactly one common point, which is a common vertex, a {touching point}, or a crossing. In this case we could prove much weaker bounds for the maximum number of edges. We also investigate $x$–monotone tangled thrackles and prove slightly better bounds.

Joint work with Janos Pach and Rados Radoicic.

November 3, 2011, 14:15h – MA B1 524

Heidi Gebauer, ETH, Zurich, “The Local Lemma is Tight for SAT”

Abstract:  The (k,s)-SAT problem involves CNF formulas where each clause has k
distinct literals and every variable occurs in at most s clauses. We investigate the maximum value f(k) such that every instance of the (k,f(k))-SAT problem is a YES-instance. The determination of this extremal function is particularly important as it represents the value where the SAT problem exhibits its complexity hardness jump: The (k, f(k) + 1)-SAT problem is already NP-hard! The (lopsided) Local Lemma gives that f(k) >= (2/e + o(1))2^k. We will show that this bound is tight by constructing appropriate CNF formulas via special binary trees.

September 16, 2011, 14:15h – MA B1 524

Igor Pak, UCLA  “How to draw in higher dimensions”

Abstract:  Fary’s classical theorem states that every planar graph can be drawn in the plane with straight edges (and without crossings). Tutte showed that under minor extra conditions, all faces can be made convex polygons. In fact, one can make all their vertices rational. But what happens in higher dimensions? Under what condition one can embed unions of topological polyhedra into space as geometric polyhedra? If yes, can one always make all vertices to be rational? I will give both positive and negative results in this direction: some easy, some difficult, but all very surprising. No background is assumed, as I will start with a lengthy review of the earlier work.
Joint work with Stedman Wilson

July 7, 2011, 14:00h – MA B1 524

Elias Tsigaridas, Aarhus University “Exact algorithms for stochastic games and real algebraic geometry”

Abstract:  Shapley’s discounted stochastic games and Everett’s recursive games are classical models of game theory describing two-player zero-sum games of potentially infinite duration.
We present an exact algorithm for solving such games based on separation bounds from real algebraic geometry. When the number of positions of the game is constant, the algorithm runs in polynomial time and is the first with this property.
If time permits. we will also present lower bounds on the algebraic degree of the values of stochastic games, induced from the irreducibility of polynomials that have coefficients that depend on the combinatorial parameters of the games, based on a generalization of Eisenstein criterion.

Joint work with
K.A. Hansen, M. Koucky, N. Lauritzen, and P.B. Miltersen.

June 3, 2011, 14:00h – MA B1 524

Dömötör Pálvölgyi, ELTE, “Unique-maximum and conflict-free colorings for hypergraphs and tree graphs”

Abstract:  We investigate the relationship between two kinds of vertex colorings of hypergraphs: unique-maximum colorings and conflict-free colorings. In a unique-maximum coloring, the colors are ordered, and in every hyperedge of the hypergraph the maximum color in the hyperedge occurs in only one vertex of the hyperedge. In a conflict-free coloring, in every hyperedge of the hypergraph there exists a color in the hyperedge that occurs in only one vertex of the hyperedge. We define corresponding unique-maximum and conflict-free chromatic numbers and investigate their relationship in arbitrary hypergraphs. Then, we concentrate on hypergraphs that are induced by simple paths in tree graphs. Our main result is that UM=O(CF)^2 for binary trees and UM=O(CF)^3 for general trees. We also present some lower bounds.
This is joint work with Panos and Keszegh.

April 19, 2011, 14:00 – MA B1 524

Pankaj K. Agarwal, Duke University, “I/O-Efficient Algorithms for Answering Level-Set and Contour Queries”

Abstract:  A terrain M is the graph of a bivariate function. We assume that M is represented as a triangulated surface with N vertices. A contour (or isoline) of M is a connected component of a level set of M. Generically, each contour is a closed polygonal curve; at “critical” levels these curves may touch each other or collapse to a point. We present I/O-efficient algorithms for the following problems: (i) Given a sequence l1,…,ls of real numbers, we present an I/O-optimal algorithm that reports all contours of M at heights l1,…,ls using O(sort(N) + T/B) I/Os, where T is the total number edges in the output contours, B is the “block size,” and sort(N) is the number of I/Os needed to sort N elements. The algorithm uses O(N/B) disk blocks. Each contour is generated individually with its composing segments sorted in clockwise or counterclockwise order. Moreover, our algorithm generates information on how the contours are nested. (ii) We can preprocess M, using O(sort(N)) I/Os, into a linear-size data structure so that all contours at a given height can be reported using O(logB N + T/B) I/Os, where T is the output size. Each contour is generated individually with its composing segments sorted in clockwise or counterclockwise order. (iii) We can preprocess M, using O(sort(N)) I/Os, into a linear-size data structure so that given a height h and a triangle t, the contour at height h that passes through t can be reported using O(logB N + T/B) I/Os, where T is the output size.

April 19, 2011, 15:15 – MA B1 524

Micha Sharir, Tel Aviv University, “From joints to distinct distances and beyond: The dawn of an algebraic era in combinatorial geometry ”

Abstract:  In November 2010 the earth has shaken, when Larry Guth and Nets Hawk Katz posted a nearly complete solution to the distinct distances problem of Erd{\H o}s, open since 1946. The excitement was twofold: (a) The problem was one of the most famous problem, as well as one of the hardest nuts in the area, resisiting solution in spite of many attempts (which only produced partial improvements). (b) The proof techniques were algebraic in nature, drastically different from anything tried before. The distinct distances problem is to show that any set of n points in the plane determine Omega(n/\sqrt{\log n}) distinct distances. (Erd{\H o}s showed that the grid attains this bound.) Guth and Katz obtained the lower bound Omega(n/\log n). Algebraic techniques of this nature were introduced into combinatorial geometry in 2008, by the same pair Guth and Katz. At that time they gave a complete solution to another (less major) problem, the so-called joints problem, posed by myself and others back in 1992. Since then these techniques have led to several other developments, including an attempt, by Elekes and myself, to reduce the distinct distances problem to an incidence problem between points and lines in 3-space. Guth and Katz used this reduction and gave a complete solution to the reduced problem. One of the old-new tools that Guth and Katz bring to bear is the Polynomial Ham Sandwich Cut, due to Stone and Tukey (1942). I will discuss this tool, including a “1-line” proof thereof, and its potential applications in geometry. One such application, just noted by Matou\v{s}ek, is an algebraic proof of the classical Szemer\’edi-Trotter incidence bound for points and lines in the plane. In the talk I will review all these developments, as time will permit. Only very elementary background in algebra and geometry will be assumed.

April 12, 2011, 15:30 – MA B1 524

Christian Ikenmeyer, University of Paderborn, “Introduction to Geometric Complexity Theory”

Abstract:  Mulmuley and Sohoni in 2001 proposed to view the P vs NP and related
problems as specific orbit closure problems and to attack them by
methods from geometric invariant and representation theory. This talk
explains some key ideas of their approach on a basic level.

March 17, 2011, 14:00h – MA B1 524

Hiroyuki Miyata, University of Tokyo, “Complete enumeration of small realizable oriented matroids”

Abstract:  Enumeration of all combinatorial types of point configurations and
polytopes is a fundamental problem in combinatorial geometry. Although many studies have been made, almost all of them are for 2-dimensional and non-degenerate cases. Recently, Finschi and Fukuda published the first database of oriented matroids including degenerate ones and of higher rank. In this talk, we present a new set of algorithms that can be applied to classify oriented matroids of moderate sizes with respect to realizability. With this new methods, we are able to enumerate all possible combinatorial types (including degenerate ones) of 3-dimensional point configurations of 8 points, 2-dimensional point configurations of 9 points and 5-dimensional point configurations of 9 points. Another successful application is the complete enumeration of combinatorial types of 5-polytopes with 9 vertices. Our classification results are available at: http://www-imai.is.s.u-tokyo.ac.jp/~hmiyata/oriented_matroids/index.html

This is a joint work with Sonoko Moriyama (Tohoku University) and
Komei Fukuda (ETH Zurich).

March 3, 2011, 15:00h – MA B1 524

Andreas Wiese, TU Berlin, “Scheduling on unrelated machines: limits of LP-approaches”

Abstract:  We study the problem of scheduling a given set of jobs on unrelated machines. For minimizing the makespan the best known approximation algorithm for this problem guarantees an approximation factor of 2. It is known to be NP-hard to approximate the problem with a better ratio than 3/2. Closing this gap has been open for 20 years and it was listed in “Polynomial time approximation algorithms for machine scheduling: Ten open problems” by Schuurman and Woeginger. All known approaches to approximate this problem are based on a natural LP- relaxation which has variables assigning jobs to machines. We explain why it is so difficult to add additional cuts that help diminishing the integrality gap. We prove this by showing that the Configuration-LP — which implicitly contains a vast class of inequalities for the natural LP — has an integrality gap of 2. This holds even for the very special case that every job can be processed on at most two machines.

Then we turn to another objective function: maximize the minimum machine load. This can be seen as allocating items to agents in order to maximize fairness. For the case that every job/item can be assigned to at most two machines/agents we give a purely combinatorial 2-approximation which is best possible, unless P=NP.

Lattice Days

Thursday. February 17, rooom CM 010:

 

14:00 – 14:45: Machine-efficient polynomial approximants (Nicolas Brisebarre) 

15:00 – 15:45: Covering cubes and closest vector (Martin Niemeier) 

16:00 – 16:30: Coffee break

16:30 – 17:15: Security of NTRUEncrypt (Damien Stehle)

Friday, February 18, room MA A1 12: 

9:30 – 10:15 : Enumerative Algorithms for the Shortest and Closest Lattice Vector Problems in Any Norm via M-Ellipsoid Coverings (Daniel Dadush)

10:30 – 11:30: L1 a new quasi-linear LLL algorithm (Andrew Novocin)

12:00 – 13:30: Lunch

13:30 – 14:15: Cutting planes for closest vector (Niemeier & Bonifas) 

14:30 – 15:30: Analysis of the BKZ reduction algorithm (Xavier Pujol)

Special semester Seminar Series

• DCG Seminar Series

Date	Time	Room	Speaker	Title
Mon, September 6	14:00	MA A1 10	Zoltan Kiraly	On a square-packing game
Mon, September 6	15:30	MA A1 10	Dömötör Pálvölgyi	Decomposition of geometric set systems and graphs
Tue, September 7	14:00	MA A1 10	Panagiotis Cheilaris	Unique-maximum and conflict-free colorings of hypergraphs
Thu, September 9	14:00	MA A3 31	Boris Bukh	Radon partitions in convexity spaces
Tue, September 14	14:00	MA A1 10	Pavel Valtr	Winkler’s pizza problem and related problems on graphs
Thu, September 16	14:00	AAC 0 06	David Wood	Crossing number and graph minors
Thu, September 16	15:30	AAC 0 06	Muriel Dulieu	Witness proximity graphs
Tue, October 5	14:00	MA A1 10	Boris Aronov	Epsilon-nets for rectangles
Thu, October 7	14:00	MA A3 31	Fabrizio Frati	On the Queue Number of Planar Graphs
Thu, October 7	15:30	MA A3 31	Edgardo Roldán-Pensado	Random convex bodies and the integer lattice
Tue, October 12	14:00	MA A1 10	Gyula Károlyi	Algebra or Geometry?
Thu, October 14	14:00	AAC 0 06	Zuzana Saferná	On the nonexistence of k-reptile tetrahedra
Thu, October 14	15:30	AAC 0 06	Stefan Felsner	Representing Graphs with Rectangles and Triangles
Tue, October 19	14:00	MA A1 10	Michael Pelsmajer	Strong Schemes
Thu, October 21	14:00	MA A3 31	Alexey Garber	Parallelohedra and the Voronoi Conjecture
Thu, October 21	15:30	AAC 0 06	Günter Rote	Crash Course on Morse Theory – Part 1
Fri, October 22	14:00	AAC 0 06	Günter Rote	Crash Course on Morse Theory – Part 2
Tue, October 26	14:00	MA A1 10	Peter Komjath	Some paradoxical colorings of Euclidean spaces
Thu, October 28	14:00	MA A3 31	Frank de Zeeuw	Rational distance sets
Thu, October 28	15:15	MA A3 31	Stefan Felsner	Representing Graphs with Rectangles and Triangles Contd.
Tue,  November 2	14:00	AAC 0 06	Ryan Schwartz	Rational Distances with Rational Angles
Tue,  November 2	15:30	AAC 0 06	Tobias Mueller	Hamilton cycles in random geometric graphs
Thu, November 4	14:00	AAC 0 06	Gyula Károlyi	Crash Course on Combinatorial Nullstellensatz – Part 1
Fri, November 5	14:00	AAC 0 06	Gyula Károlyi	Crash Course on Combinatorial Nullstellensatz – Part 2
Mon, November 8	14:00	AAC 0 06	Gyula Károlyi	Crash Course on Combinatorial Nullstellensatz – Part 3
Tue, November 9	14:00	MA A1 10	Jozsef Solymosi	Geometric problems on Cartesian products
Thu, November 11	14:00	AAC 0 06	Daniel Werner	Parameterized Complexity and Ham-Sandwich Cuts
Thu, November 11	15:30	AAC 0 06	Viola Meszaros	Separated matchings
Tue, November 16	14:00	MA A1 10	Zoltan Lorant Nagy	Permutations, hyperplanes and polynomials
Tue, November 16	15:30	AAC 0 06	Vincent Pilaud	Polytopality and Cartesian products
Thu, November 18	14:00	AAC 0 06	Nabil H. Mustafa	Crash Course on Epsilon Nets – Part 1
Fri, November 19	14:00	AAC 0 06	Nabil H. Mustafa	Crash Course on Epsilon Nets – Part 2
Tue, November 23	14:00	MA A1 10	Imre Bárány	Very colourful theorems
Thu, November 25	14:00	AAC 0 06	Miklós Simonovits	How to compute the volume in high dimension ?
Thu, November 25	15:30	AAC 0 06	Natan Rubin	Line Transversals Redux
Thu, December 9	14:00	MA A3 31	Katalin Vesztergombi	Distance of large graphs
Tue, December 14	14:00	MA B1 524 (coffee room)	Nabil Mustafa	Geometric Applications of a Randomized Optimization Technique
Thu, December 16	14:00	AAC 0 06	Jozsef Solymosi	On the Erdos distinct distance problem in the plane
Thu, December 16	15:30	AAC 0 06	Adrian Dumitrescu	Dispersion in disks

June 25, 2010, 14:15h – MA A1 11

Francisco Santos, Universidad de Cantabria, “A counter-example to the Hirsch conjecture”

 The Hirsch conjecture, stated in 1957, said that if a polyhedron is defined by $n$ linear inequalities in $d$ variables then its combinatorial diameter should be at most $n-d$. That is, it should be possible to travel from any vertex to any other vertex in at most $n-d$ steps (traversing an edge at each step). The conjecture was posed and is relevant in the context of the simplex method in linear programming. The simplex method, after all, finds the optimal solution by moving from vertex to vertex along the edges of the feasibility polyhedron. Experimentally, the simplex method usually finishes in a linear number of steps, but examples where certain choices of pivot rules lead to exponentially long paths exist, and no pivot rule is known that can be proved to always finish in a polynomial number of steps. Even if other methods for linear programming are proved to be polynomial (Karmakar, Khachiyan), the simplex method remains one of the methods most often used in practice. From a complexity theory point of view, it is also significant that the known methods are polynomial in the “bit complexity” model, but a polynomial pivot rule for the simplex method would provide a “strongly polynomial” algorithm, that is, one that is polynomial also in the “real machine” model. The question whether such a “strongly polynomial” method exists for linear programming was included by S. Smale in his list of “Mathematical problems for the next century” (AMS, 2000). Of course, a polynomial pivot rule can only exist if the combinatorial diameter is polynomially bounded. The unbounded case was disproved by Klee and Walkup in 1967. In this talk I will describe the construction of the first counter-example to the bounded case (a polytope).

June 8, 2010, 14:00h – MA A1 11

Joel Spencer, Courant Institute (New York), “From Erdos to Algorithms”

 

The probabilistic method, as developed by the Paul Erd\H{o}s, proves the existence of a combinatorial object. Giving an effective algorithm to actually find the object has been a vexing problem, particularly when the original proof shows that a random object is successful with exponentially small probability. Very recently there have been two great successes.

Six Standard Deviations Suffice:
Let A=(a_{ij}) be an n by n matrix with all |a_{ij}| <= 1. A quarter century ago I showed that there exists x=(x_1,…,x_n) with all x_i=+-1 so that, setting Ax=(E_1,…,E_n), all |E_j|<=K\sqrt{n}. Here K is an absolute constant somewhat less than 6. When all a_{ij}\in{0,1} this is, combinatorially, two coloring n points so that n sets all have discrepency less than K\sqrt{n}.) Now Nikhil Bansal (IBM) has given an algorithm based on Semidefinite Programming to actually find (with perhaps a worse K) such an x in polynomial time.

Lovász Local Lemma:
Let a family S_1,…,S_n of k-element sets be given, such that each set overlaps at most d others. Assume ed2^{1-k}<1 but make no assumption on n. About thirty five years ago Lovász gave a sieve method that implied the existance of a two coloring of the underlying vertices so that no set was monochomatic. Now Robin Moser (ETH graduate student (!)) with the assistance of Gábor Tardos (Rényi Institute) have found a simple algorithm (with a subtle proof that it works!) to actually find the coloring.

May 6, 2010, 14:00h – GRA331

Peter Mani-Levitska, Bern, “Another way of answering Henri Poincare`s fundamental question”

After G. Perelman’s solution of the Poincare Conjecture, this is a different way toward it. Given a simply connected, closed 3-manifold M, we produce a homotopy disc H, which arises from M by a finite sequence of simple modifications and, almost miraculously, can be imbedded into the ordinary space R^3. It follows that H is a disc, hence M is a sphere. In order to construct H, we use a special stratification of M, based on the fact that M is simply connected.

April 29, 2010, 14:00h – MA A1 10

Denis Naddef, Grenoble INP-Ensimag, France, “Closed set form Inequalities for the Traveling Salesman Polytope”

Closed set form Inequalities or hypergraph inequalities, for the Traveling Salesman Polytope play an important in Branch and Cut codes to solve the Symmetric Traveling Salesman Problem. An inequality is said to be in closed set form if it is described by a hypergraph and integer weights on the edges of the hypergraph. We impose the extra condition that the right hand side does not depend on the number of nodes concerned by the hypergraph. This last condition is one of the differences between closed set form Inequalities and hypergraph inequalities. So far only non negative integer coefficients on the edges were considered. We show that the use of negative coefficient is necessary to obtain some facet inducing inequalities.

April 22, 2010, 14:00h – MA A1 11

Giuseppe Liotta, “The Hamiltonian Augmentation Problem and its Applications to Graph Drawing”

In this talk I will digress about the strict interplay between the graph-theoretic problem of computing a hamiltonian augmentation of a planar graph $G$ and the graph drawing problem of embedding $G$ onto a given set of points. We review different hamiltonian augmentation techniques and their impact on different variants of the corresponding graph drawing problem. We also look at universal point sets, simultaneous graph embeddings, and radial graph drawings. Some challenging open problems will also be discussed.

April 15, 2010, 14:00h – MA A1 11

Micha Sharir, School of Computer Science Tel Aviv University, “Improved bounds for geometric permutations in higher dimensions”

  We show that n arbitrary pairwise disjoint convex sets in three dimensions admit at most O(n^3\log n) geometric permutations (i.e., orders in which they are all met by a line). This improves Wenger’s 20-years-old bound of O(n^4) (but is still short of the best known lower bound of Omega(n^2)). The result extends to any higher dimension.

Joint work with Natan Rubin and Haim Kaplan.

March 18, 2010, 14:00h – MA A1 11

Ján Foniok, “Pivoting algorithms and unique-sink orientations“

We are given the edge graph of an n-dimensional hypercube and its orientation; each face of the hypercube has a unique sink. The orientation is given implicitly, i.e., for every vertex we can ask an oracle to tell us the orientation of all incident edges. We are looking for an algorithm that finds the unique sink of the hypercube fast (“fast” means the number of queries to the oracle is bounded by a polynomial in the dimension n). It has been shown that linear programs (Gartner, Schurr, 2006) and some linear complementarity problems (Stickney, Watson, 1978) can be reduced to finding the sink of special unique-sink orientations. Hence, in fact, we are interested in algorithms for these special classes of USOs. Such a fast algorithm would in turn provide a strongly polynomial algorithm for linear programming (or some linear complementarity problems). Some algorithms follow a directed path in the hypercube; they correspond to pivoting algorithms. The best known algorithms, however, are “random access”. I will discuss some deterministic and some randomised algorithm, and show a couple of both positive and negative results and several open problems.

Various parts are joint work with some of these collaborators:
Komei Fukuda, Bernd Gartner, Lorenz Klaus, Hans-Jakob Luthi.

March 11, 2010, 14:15h – MA A1 10

Zoltán Füredi, Renyi Institute, Budapest and UIUC, Urbana-Champaign, IL, USA, “Coin-weighing and different directions of lines“

Starting with a version of coin-weighting problems of ApSimon (1984) we discuss directions of lines among lattice points. Consider a set V of k vectors on the plane with nonnegative integer coordinates. Let S(V) be the set of the 2^k-1 non-empty subset sums. We are looking for the smallest N(k) such that V is a subset of NxN and the slopes of the members of S are all distinct.

February 25, 2010, 14-15h – MA A1 10

Klaus Jansen, “An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables”

We present an efficient polynomial time approximation scheme (EPTAS) for scheduling on uniform processors, i.e. finding a minimum length schedule for a set of $n$ independent jobs on $m$ processors with different speeds (a fundamental NP-hard scheduling problem). The previous best polynomial time approximation scheme (PTAS) by Hochbaum and Shmoys has a running time of $(n/\epsilon)^{O(1/\epsilon^2)}$. Our algorithm, based on a new mixed integer linear programming (MILP) formulation with a constant number of integral variables and an interesting rounding method, finds a schedule whose length is within a relative error $\epsilon$ of the optimum, and has running time $2^{O(1/\epsilon^2 \log(1/\epsilon)^3)} + poly(n)$.

February 4, 2010, 14:15h – MA A1 10

Jean Cardinal, “Sorting under Partial Information (without the Ellipsoid Algorithm)”

 

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. However, their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it unpractical.
We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed in a restricted class of graphs. All our algorithms are simple to implement.
This is a joint work with Samuel Fiorini, Gwenaël Joret, Raphaël Jungers, and J. Ian Munro.

January 28, 2010, 14:15h – MA A1 11

Peter Bürgisser, “On a Problem Posed by Steve Smale”

  The 17th of the problems proposed by Steve Smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of $n$ complex polynomials in $n$ unknowns in time polynomial, on the average, in the size $N$ of the input system. A partial solution to this problem was given by Carlos Beltran and Luis Miguel Pardo who exhibited a randomized algorithm doing so. In this paper we further extend this result in several directions. Firstly, we exhibit a linear homotopy algorithm that efficiently implements a non-constructive idea of Mike Shub. This algorithm is then used in a randomized algorithm, call it LV, a la Beltran-Pardo. Secondly, we perform a smoothed analysis (in the sense of Spielman and Teng) of algorithm LV and prove that its smoothed complexity is polynomial in the input size and $\s^{-1}$, where $\s$ controls the size of of the random perturbation of the input systems. Thirdly, we perform a condition-based analysis of LV. That is, we give a bound, for each system $f$, of the expected running time of LV with input $f$. In addition to its dependence on $N$ this bound also depends on the condition of $f$. Fourthly, and to conclude, we return to Smale’s 17th problem as originally formulated for deterministic algorithms. We exhibit such an algorithm and show that its average complexity is $N^{O(\log\log N)}$. This is nearly a solution to Smale’s 17th problem.

This is joint work with Felipe Cucker.

January 26, 2010, 14:00, BC 2.29

Damien Stehlé, CNRS, Is lattice-based cryptography becoming practical?

  Lattice-based cryptography started in the mid 1990’s, with the pioneering works of Ajtai on the Shortest Vector Problem, and with the novel GGH and NTRU cryptosystems. It has now become an extremely active branch of cryptography, thanks to a unique combination of attractive features. Lattice-based cryptographic primitives are often simple and elegant, they are very flexible and also possibly quite efficient. But above all, they provide unprecedented notions of security: breaking the primitive would provide efficient algorithms for worst-case instances of problems closely related to NP-hard problems. A popular security feature is its apparent resistance to quantum computers. In this talk, we will survey the computational problems underlying lattice-based cryptography and describe a few schemes.  By considering the state-of-the-art attacks and studying recently introduced schemes that are asymptotically very efficient, we will attempt to assess the practicality of lattice-based cryptography.

December 3, 2009, 14:15h – MA A1 10

Gábor Tardos, “Limits of trees”

 

Analogously to the work of Borgs, Chayes, Lovasz, Sos, Szegedy and Vesztergombi for limits of dense graphs we propose a theory for limits of trees. Consider the following simple procedure for sampling: uniformly select k edges of the tree and form the sample by contracting all other edges. The sampling procedure naturally defines a local distance on finite trees. We introduce a global distance and prove that the two distances are equivalent (like the Frieze-Kannan cut-distance in the case of dense graphs). The natural limit objects are certain compact real trees equipped with an additional probability measure. These are well studied objects (Aldous, Evans, Winter and others) and form a separable compact space with respect to the Gromov-Prohorov metric, which coincides with the global metric mentioned above. Sampling real trees can be naturally defined and we prove that a sampling sequence of finite trees of increasing size converges to the original real tree with probability one. (Joint work with Gabor Elek.)

November 26, 2009, 14:15h – MA A1 10

Arash Rafiey, “Proper interval digraphs, min-max orderings, and their connection with minimum cost homomorphism problem”

 

Digraphs with Min-Max orderings are digraph analogues of proper interval graphs and bigraphs. They can be equivalently described by a geometric representation with two inclusion-free families of intervals, and we call them monotone proper interval digraphs. We give a forbidden structure characterization of monotone proper interval digraphs which implies a polynomial time recognition algorithm. We show the connection of these digraphs with an optimization problem, so called minimum cost homomorphism problem. The minimum cost homomorphism problem is motivated by a real-world problem in defence logistics.

October 15, 2009, 14:15h – MA A1 10

Alain Hertz, École Polytechnique de Montréal, Canada, “Total Domination and the Caccetta-Häggkvist Conjecture”

A total dominating set in a digraph G is a subset W of its vertices such that every vertex of G has an immediate successor in W. The total domination number of G is the size of the smallest total dominating set. We consider several lower bounds on the total domination number and conjecture that these bounds are strictly larger than g(G)-1. where g(G) is the number of vertices of the smallest directed cycle contained in G. We prove that these new conjectures are equivalent to the Caccetta-Häggkvist conjecture which asserts that g(G)-1 0.

September 16, 2009, 14:15h – MA11

David Pritchard, “Hypergraphic LP Relaxations for the Steiner Tree Problem”

The Steiner Tree problem is to find a cheapest subgraph connecting a given set of terminals. We study its linear program (LP) relaxations. A novel LP tool, uncrossing of partitions, yields (1) equivalence of several known hypergraphic LP relaxations and equivalence to the bidirected cut relaxation when terminals form a dominating set (quasi-bipartite graphs) (2) on quasi-bipartite graphs, the integrality gap is at most 73/60 (3) basic solutions are sparse and other structural results.

This is joint work with Jochen Könemann and Deeparnab Chakrabarty.

July 30, 2009, 14:00h – MA11

Rico Zenklusen,“A Flow Model Based on (Poly-)Linking Systems”

We introduce a flow model based on linking systems that generalizes several other flow models, including an information flow model [Avestimehr, Diggavi and Tse, Allerton’07] for which an efficient maximum flow algorithm was recently found [Amaudruz and Fragouli, SODA’09]. The flow networks we consider have a layered structure and how flow can be sent from one layer to the next one is described by linking systems, a structure closely related to matroids. The model can be generalized to a capacitated version by using polylinking systems instead of linking systems. However, for the sake of simplicity, we concentrate on linking systems in the presentation. Exploiting results from matroid theory, many interesting properties can be derived. In particular we show a max-flow min-cut theorem, submodularity of cut values, and a description of the flow polytope. Furthermore, we show how to determine a maximum flow, minimum cost flow and a minimum cut in polynomial time.

This is joint work with Michel Goemans and Satoru Iwata.

June 4, 2009, 14:15h – MA 11

Endre Szemerédi, Renyi Institute, Budapest and Rutgers University, New Brunswick, “Upper bound on the size of a sequence of positive integers with the property that the sum of two elements is never a square number.”

Let S\subseteq [1,n] be a set of positive integers with the property that the sum of no two elements of S is a square number. We are going to prove that S can be covered by the union 11 suitably chosen residue classes mod 32, and that this result is tight. The proof uses combinatorial, analytical, and linear programming methods.

This is a joint work with Ayman Khalfallah.

May 28, 2009, 14:15h – MA A1 11

Adrian Dumitrescu, University of Wisconsin, “On stars and Steiner stars”

A Steiner star for a set P of n points in R^d connects an arbitrary point in R^d to all points of P, while a star connects one of the points in P to the remaining n-1 points of P. All connections are realized by straight line segments. Let the length of a graph be the total Euclidean length of its edges. Fekete and Meijer showed that the minimum star is at most $\sqrt{2}$ times longer than the minimum Steiner star for any finite point configuration in R^d. The supremum of the ratio between the two lengths, over all finite point configurations in R^d, is called the star Steiner ratio in R^d. It is conjectured that this ratio is $4/\pi = 1.2732\ldots$ in the plane and $4/3=1.3333\ldots$ in three dimensions. Here we give upper bounds of $1.3631$ in the plane, and $1.3833$ in 3-space. These estimates yield improved upper bounds on the maximum ratios between the minimum star and the maximum matching in two and three dimensions. We also verify that the conjectured bound $4/\pi$ in the plane holds in two special cases. Our method exploits the connection with the classical problem of estimating the maximum sum of pairwise distances among n points on the unit sphere, first studied by Laszlo Fejes Toth. It is quite general and yields the first non-trivial estimates below $\sqrt2$ on the star Steiner ratios in arbitrary dimensions. We show, however, that the star Steiner ratio in R^d tends to $\sqrt{2}$ as d goes to infinity. As it turns out, our estimates are related to the classical infinite Wallis product.

Joint work with Csaba D. Toth and Guangwu Xu.

May 20, 2008, 14:15h – MA 11

Géza Tóth, Renyi Institute, “The Erdos-Szekeres theorem with forbidden order types”

According to the Erd\H os-Szekeres theorem, among n points in general position, there are always c log n in convex position, and this bound cannot be improved asymptotically. We investigate the following question. Is it possible to improve the c log n bound, if we assume that our set of n points does not contain a certain type of subconfiguration? As an example, here is a trivial statement. Suppose that our point set does not contain a four point subconfiguration whose convex hull is a triangle. Then all the points are in convex position, that is, among n such points, instead of c log n, there are n points in convex position. We show that for certain configurations there is an better bound then c log n, but for certain other configurations the bound does not get essentially better.

Joint work with Gyula Karolyi.

May 14, 2008, 14:15h – MA 11

Samuel Fiorini, “An Efficient Algorithm for Partial Order Production”

We consider the problem of partial order production: arrange the elements of an unknown totally ordered T into a target partially ordered set S, by comparing a minimum number of pairs in T. Special cases of this problem include sorting by comparisons, selection, multiple selection, and heap construction.
We give an algorithm performing ITLB + o(ITLB) + O(n) comparisons in the worst case. Here, n denotes the size of the ground sets, and ITLB denotes a natural information-theoretic lower bound on the number of comparisons needed to produce the target poset.
The overall complexity of our algorithm is polynomial. This answers a question of Yao (SICOMP, 1989).
Our strategy is to extend the poset S to a weak order W whose corresponding information-theoretic lower bound is provably not much larger than that for S. Taking W instead of S as a target poset, we then solve the problem by applying a multiple selection algorithm that performs not much more than ITLB comparisons. We base our analysis on the entropy of the target poset S, a quantity that can be efficiently computed and provides a good estimate of ITLB since the latter is, up to a linear error term, n times the entropy of S.
This is joint work with Jean Cardinal (ULB), Gwenaël Joret (ULB), Raphaël M. Jungers (UCL), Ian Munro (Waterloo)

May 8, 2009. 14:15h – MA A1 10

Martin Skutella, “Recent results on unsplittable and k-splittable flows in single- source networks”

Given a network with a single source and several sinks with associated demands, we study flow problems with restrictions on the flow-carrying paths. In the unsplittable flow problem, the demand of each sink has to be sent along a single source-sink path. The k-splittable flow problem allows to split each demand into at most k packets such that each packet is sent along a single source-sink path. We discuss recent results and algorithms for turning an arbitrary flow into an unsplittable or k-splittable flow with bounded increase of flow values along arcs.

May 7, 2009, 14:15h – MA 11

Imre Bárány, “On the power of linear dependences”

I will talk about an old result, the so called vector-sum theorem and plan to explain how linear algebra can help solving various geometric problems. Several examples will illustrate the power of this technique, and some applications will also be presented.

April 30, 2009, 14:15h – MA A1 12

David Avis, McGill University, “The shelling property for polytopal digraphs”

A polytopal digraph G(P) is an orientation of the skeleton of a convex polytope P. The possible non-degenerate pivot operations of the simplex method in solving a linear program over P can be represented as a special polytopal digraph known as an LP digraph. Presently there is no general characterization of which polytopal digraphs are LP digraphs, although three necessary properties are well known: acyclicity, unique sink orientation(USO), and the Holt-Klee property. We introduce a fourth property: the shelling property. For each d ≥ 4 and n ≥ d +2, we construct a polytopal digraph for a polytope P in dimension d with n vertices which is an acyclic USO that satisfies the Holt-Klee property, but does not satisfy the shelling property. Such examples cannot exist for other values of n and d. Joint work with H. Miyata and S. Moriyama.

April 23, 2009, 14:15h – MA A1 12

Boris Bukh, Princeton University, “Geometric selection theorems”

In combinatorial geometry one frequently wants to select a point or a set of points that meets many simplices of a given family. The two examples are choosing a point in many simplices spanned by points of some P in R^d, and choosing a small set of points which meets the convex hull of every large subset of P (the weak epsilon-net problem). I will present a new class of constructions that yield the first nontrivial lower bound on the weak epsilon-net problem, and improve the best bounds for several other selection problems. Joint work with Jiri Matousek and Gabriel Nivasch.

April 6, 2009, 14:15h – MA A1 12

Guy Even, Tel Aviv University, “A Strongly Polynomial Algorithm for Controlled Queues”

We consider the problem of computing optimal policies of finite-state, finite-action Markov Decision Processes (MDPs). A reduction to a continuum of constrained MDPs (CMDPs) is presented such that the optimal policies for these CMDPs constitute a path in a graph defined over the deterministic policies. This path contains, in particular, an optimal policy of the original MDP. We present an algorithm based on this new approach that finds this path and thus an optimal policy. In the general case this path might be exponentially long in number of states and actions. We prove that the length of this path is polynomial if the MDP satisfies a coupling property. Thus we obtain a strongly polynomial algorithm for MDPs that satisfy the coupling property. We prove that discrete time versions of controlled M/M/1 queues induce MDPs that satisfy the coupling property. The only previously known polynomial algorithm for controlled M/M/1 queues in the expected average cost model is based on linear programming (and is not known to be strongly polynomial). Our algorithm works both for the discounted and expected average cost models, and the running time does not depend on the discount factor.

No prior familiarity with MDPs will be assumed in the talk.

Joint work with Alexander Zadorojniy and Adam Shwartz.

March 19, 2009, 15:15h – MA A1 11

Diana Piquet, Charles University in Prague and TU Munich, “The Loebl-Komlos-Sos conjecture”

The Loebl-Komlos-Sos conjecture asserts that every graph with median degree k contains any tree of order k+1. Recently significant progress has been made towards the solution of this conjecture by Cooley, Hladky, Piguet, Simonovits, Stein, and Szemeredi. I shall talk about the solution for dense graphs, as well as about the techniques needed to handle sparse graphs

March 19, 2009, 14:15h – MA A1 11

Jan Hladký, Charles University in Prague and TU Munich,  “Embedding thin three-colorable graphs”

We investigate under which minimum-degree condition does a graph G contain a square-path and a square-cycle of a certain length. We give precise thresholds, assuming that the order of G is large. This extends results of Fan and Kierstead [J. Combin. Theory Ser. B, 67(2), 167-182, 1996] and of Komlos, Sarkozy, and Szemeredi [Random Structures Algorithms, 9(1-2), 193-211, 1996] concerning containment of a spanning square-path and a spanning square-cycle, respectively. The method also yields optimal minimum-degree threshold for the problem of embedding a three-colorable graph H of bounded maximum degree and sublinear bandwidth in the case that the order H is a fraction of the order of the hosting graph G. This can be viewed as a version of the Bollobas-Komlos Conjecture, solved recently by Bottcher, Schacht and Taraz [J. Combin. Theory Ser. B, 98(4), 752-777, 2008], [Math. Ann, 343(1), 175-205, 2009]. This is joint work with Peter D. Allen, and Julia Boettcher.

 

March 2, 2009, 14:00h – MA A1 12

Christophe Weibel, “Minkowski sums of polytopes with maximum number of vertices”

Minkowski sum is a basic operation with applications in all kinds of fields. The combinatorial properties of sums of polytopes are however not well known. We present in this talk some recent results and bounds on the number of vertices and facets of sums of polytopes. In particular, we prove the exact maximal number of faces for sums of any number of 3-dimensional polytopes. We also present a conjecture on vertices in higher dimensions.

February 26, 2009, 14:15h – MA A1 11

Günter Rote, FU Berlin, “Two applications of weighted point matching”

The two following problems can be solved by a reduction to a minimum-weight bipartite matching problem (or a related network flow problem):

1. Floodlight illumination: We are given n infinite wedges (sectors) that can cover the whole plane when placed at the origin. They are to be translated on n given locations (in arbitrary order, but without rotation) such that they still cover the whole plane. (This extends results of Bose et al. 1997.)
2. Convex partition: n points inside a convex n-gon are to be assigned to the n sides such that the n triangles formed by each side with its associated point are disjoint. (Garcia and Tejel 1995, Aurenhammer 2008)

February 12, 2009, 14:15h – MA A1 12

Robin Moser, ETH Zürich, “Constructive Lovasz Local Lemma”

The Lovàsz Local Lemma [Erdös, Lovàsz, 1975] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In his breakthrough paper [Beck, 1991], Beck demonstrated that a constructive variant can be given under certain more restrictive conditions. Simplifications of his procedure and relaxations of its restrictions were subsequently exhibited in several publications [Alon; Molloy and Reed; Czumaj, Scheideler; Srinivasan; M]. 
In this talk, a new algorithm is presented that can find the object guaranteed to exist by the Local Lemma in polynomial time. In contrast to all previous approaches, the new algorithm applies to almost all known applications of the lemma and since the original non-constructive proofs are not invoked anymore, it can be regarded as a constructive proof variant.
 

February 5, 2009, 11:15h – Room: MA A1 12

Christian Sohler, University of Paderborn, “Coresets and Sketches for High Dimensional Subspace Approximation Problems”

Given a point set P a subspace approximation problem asks for a subspace that minimizes a certain objective function, for example, the sum of distances to the subspace. In this talk, we develop techniques for subspace approximation problems that deal with massive data sets. In particular, we develop coresets and sketches for the linear subspace approximation problem, i.e. small space representations that approximate the input point set P with respect to a subspace approximation problem. Using these techniques, we develop new approximation algorithms and data streaming algorithms for subspace approximation.
Joint work with Dan Feldman (Tel Aviv University), Morteza Monemizadeh (U. Bonn), and David Woodruff (IBM Almaden).

December 19, 2008, 14:15h – MA A1 10

Konrad Swanepoel, TU Chemnitz, “Distance problems in Euclidean and normed spaces”

This talk will be a survey of the unit distance problem of Erdös in high-dimensional Euclidean and normed spaces and related affine problems, such as the number of antipodal pairs in a set of points (joint work with B. Csikos, G. Kiss and O. de Wet). I will also say a little about the distinct distance problem in normed spaces.

December 18, 14:15h – MA A1 10

Paul Dütting, EPFL, “Multi-Unit Auctions With Budget Limits” of Dobzinski, Lavi & Nisan

In practice bidders participating in an auction typically have budget limits. If there is only one item for sale, then there exists a unique incentive-compatible and pareto-optimal mechanism. If there is more than one item, however, such a mechanism does not exist. This talk demonstrates why.

December 11, 14:15h – MA A1 10

Uli Wagner, ETH Zürich, “Hardness of embedding simplicial complexes in R^d”

It is well known that one can test in linear time whether a given graph is planar. We consider the higher-dimensional generalization of this problem: given a k-dimensional simplicial complex K and a target dimension d, does K embed into R^d? Surprisingly, rather little seems to be known about the algorithmic aspects of this problem. (All the relevant topological notions will be defined and explained during the talk, at least on an intuitive level.) Known results easily imply that the problem is solvable in polynomial time if k=d=2 or d=2k >= 6. We observe that the problem is algorithmically undecidable for k=d-1 and d >= 5. This follows from a famous result of Novikov on the unsolvability of recognizing the 5-sphere. Our main result is NP-hardness in the range d >= 4 and d >= k >= (2d-2)/3. These dimensions fall outside the so-called metastable range of a theorem of Haefliger and Weber, which characterizes embeddability in terms of the so-called deleted product obstruction. Our reductions are based on examples, due to Segal, Spiez, Freeman, Krushkal, Teichner, and Skopenkov, showing that outside the metastable range, the deleted product obstruction is insufficient.
Joint work with Jiri Matousek and Martin Tancer.

December 4, 14:15 – CM 011

Johannes Blömer, University of Paderborn, Germany , “Clustering for general distance measures”

Clustering is the (meta-)problem of partitioning a given set of objects into subsets of similar objects. It has application in various areas of computer science such as machine learning, data compression, data mining, or pattern recognition. Depending on the application we want to cluster such diverse objects as text documents, probability distributions, feature vectors, etc. Obviously, different objects and different applications also require different notions of (dis-)similarity of objects. In the talk I will present clustering algorithms that are applicable to a large class of distance measures. The main focus will be on the following question: Which techniques that have been successfully applied in a geometric setting, i.e. for the Euclidean or the squared Euclidean distance, can be applied to more general distance measures like the Kullback-Leibler divergence from information theory.

November 20, 2008, 13:00h – CM 011

Yves Brise, ETH Zürich, “Violator Spaces – an optimization framework”

Violator Spaces are an abstract optimization framework that stands in line with LP-type problems and Linear Programming, each of which is a proper generalization of the previous one. In this talk, the standing example of a violator space will be the problem of computing the smallest enclosing ball of n given points in R^d. There is an algorithm, called Clarkson’s algorithm, that computes the optimal solution of a violator space in expected O(dn + f(d)) basic operations, where f(d) is an arbitrary function of d, and putting dn is actually cheating a bit. The talk focuses on the inner workings of Clarkson’s algorithm (e.g. what I mean by cheating) and some open problems.

November 18, 2008, 14:15h – BM 1111

Sanjeeb Dash, IBM T.J. Watson Research Center, N.Y., “Mixed-integer rounding cuts: separation and complexity”

Mixed-integer rounding (MIR) cuts are known to be very useful in solving mixed-integer programming problems. Balas and Saxena (2007), and independently, Dash, Gunluk and Lodi (2008), show that optimizing over the set of points satisfying all MIR cuts of a mixed-integer program (MIP), by iteratively finding violated MIR cuts, yields strong lower bounds for problems in the MIPLIB 3.0 library. Both groups of authors solve a non-trivial auxiliary MIP to find a single violated MIR cut, and this often takes a lot of time. In this talk we discuss a heuristic to find violated rank-1 MIR cuts which is much faster than the separation methods in the papers by Balas and Saxena, and Dash, Gunluk and Lodi. Further, the lower bounds obtained by our heuristic are not significantly weaker than those in the above papers. This is joint work with Marcos Goycoolea. We then discuss mixing inequalities (Gunluk and Pochet 2001), which can be viewed as a generalization of MIR cuts. We show that each mixing inequality can be derived via a short MIR cutting-plane proof. We thereby conclude that cutting-plane proofs which use mixing inequalities have exponential complexity in the worst case, based on a similar result for MIR proofs. This is a joint work with Oktay Gunluk.

October 16, 14:15h – MA A1 10

Khaled Elbassioni, MPI Saarbrücken, Germany, “On the approximability of the maximum feasible subsystem problem with 0/1-coefficients”

Given a system of constraints l_i ≤ a_i^Tx ≤ u_i, where a_i ∈ {0,1}ⁿ, and l_i, u_i ∈ R₊, for i=1,…m, we consider the problem RMFS of finding the largest subsystem for which there exists a feasible solution x ≥ 0. We present approximation algorithms and inapproximability results for this problem, and some of its important special cases. Our main conclusions are (I) There exists a sharp separation in the approximability between the case when L= max{l₁, …, l_m} is bounded above by a polynomial in n and m, and the case when it is not. (II) for the case where the constraint matrix has the consecutive ones property, there exists a sharp separation in approximability between the case where we allow a violation of the upper bounds by at most a (1 + ε) factor, for any fixed ε > 0, and the case when no violations are allowed. We will give an application of this RMFS problem to a recently studied profit-maximizing pricing problem. This is joint work with Rajiv Raman, Saurabh Ray, and Rene Sitters.

October 9, 14:00h – MA A1 10

András Sebő, CNRS, Laboratoire G-SCOP, Grenoble, “Path partitions, cycle covers and integer decomposition of stable sets”

A polyhedron P has the integer decomposition property, if every integer vector in kP is the sum of k integer vecors in P. We explain why coflow polyhedra defined by Cameron and Edmonds have the integer decomposition property, and apply ithis result to the convex hull of particular stable sets in graphs. Therebye we prove a generalization of Greene and Kleitman’s well-known theorem on posets to arbitrary digraphs which implies recent and classical purely graph theoretical results on cycle covers, and is closely related to conjectures of Berge and Linial on path partitions.

October 9, 15:00h – MA A1 10

András Gyárfás, CNRS, Laboratoire G-SCOP, Grenoble and Hungarian Academy of Sciences Budapest, Hungary, “Large monochromatic connected pieces in edge colorings of graphs – a survey”

A first exercise in Graph Theory can easily be – in fact it is in Bollobas’s Modern Graph Theory – that either the graph or its complement is connected. This remark of Erdos and Rado often considered as folklore – no wonder since its validity is obvious to anyone who understand the statement. An equivalent formulation is that in any 2-coloring of the edges of a complete graph, there is a monochromatic spanning tree. My aim is to survey results, problems and proof methods grown from this remark during the last forty years.

• type of spanning trees – height two trees, octopuses, brooms
• diameter – “small world”, stars, double stars
• higher connectivity – finding a highly connected large piece
• Gallai colorings – an extension of 2-colorings
• many colors – colorings from affine spaces
• fine tuned results
• local colorings
• hypergraph colorings

 

October 3, 15:00h – MA A3 31

François Margot, Carnegie Mellon University, Pittsburgh, USA , “Convexification for Mixed Integer Nonlinear Problems”

Many industrial problems can be naturally formulated using Mixed Integer Nonlinear Programming (MINLP). Motivated by the demand for Open-Source solvers for real-world MINLP problems, we have developed a spatial Branch-and-Bound software package named couenne (Convex Over- and Under-ENvelopes for Nonlinear Estimation). In this talk, we present the structure of couenne and discuss in detail our work on two of its components: bounds tightening and branching strategies. We then present experimental results on a set of MINLP instances including some industrial applications. We also compare the performance of couenne with a state-of-the-art solver for nonconvex MINLPs. Joint work with P. Belotti (Lehigh) L. Biegler, G. Cornuejols, I. Grossman (all CMU) P. Bonami (LIF, Marseille) J. Lee, A. Waechter (both IBM) L. Liberti (LIX, Paris)

October 2, 14:15h – MA A1 10

Hans Raj Tiwary, Saarland University, Germany, “Self-duality of Polytope: Relations to Vertex Enumeration and Graph Isomorphism”

I will discuss the complexity of determining whether a polytope given by its vertices or facets is combinatorially isomorphic to its polar dual. I will show that this problem is Graph Isomorphism hard, and that it is Graph Isomorphism complete if and only if Vertex Enumeration is Graph Isomorphism easy. The constructions employed in the proof yield a class of self-dual polytopes that are interesting on their own. In particular, this class of self-dual polytopes has the property that their facet-vertex incident matrix is transposable if and only if the matrix is symmetrizable as well. As a consequence of this construction, we also prove that checking self-duality of a polytope, given by its facet-vertex incidence matrix, is Graph Isomorphism complete, thereby answering a question of Kaibel and Schwartz.

September 18, 14:15h – MA A1 10

Gabor Tardos, Simon Fraser University, Vancouver, Canada, “Local chromatic number of graphs”

A vertex coloring of a graph is a local k-coloring if the neighborhood of every vertex contains fewer than k colors. The local chromatic number of a graph G is the smallest k such that G has a proper local k-coloring. This parameter is clearly bounded by the chromatic number but it can be arbitrarily smaller. We survey several results on this interesting graph parameter, including results on the local chromatic number of specific graph families (Kneser, Schrijver, Mycielski and shift graphs) and graphs on surfaces.

September 10, 2008, 14:15h – MA 12

Lijun Zhang, Saarland University, Germany, “Decision Algorithms for Probabilistic Simulations”

Probabilistic phenomena arise in embedded, distributed, networked, biological and security systems, and are accounted for by various probabilistic modeling formalisms based on labelled transition systems.

Among the most popular ones are homogeneous discrete-time and continuous-time Markov chains (DTMCs and CTMCs) and their extensions with nondeterminism, which we will consider in this talk. Simulation relations admit to compare the behavior of two models and provide the principal ingredients to perform abstractions of the models while preserving interesting properties. Intuitively, a model simulates another model if it can imitate all of its moves. Simulation preorders are transitive and compositional, thus allowing hierarchical verification and decomposition of difficult verification tasks into several subproblems. Recently, variants of simulation relations, such as simulatability and polynomially accurate probabilistic simulations, have been introduced to prove soundness of security protocols. The focus of this talk lies on decision algorithms for various simulation preorders of probabilistic systems. We propose efficient decision algorithms.

August 26, 2008, 14:15h – MA 12

Jaroslaw Byrka, TU Eindhoven and CWI Amsterdam, The Netherlands, “An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem”

We obtain a 1.5-approximation algorithm for the metric uncapacitated facility location problem (UFL), which improves on the previously best known 1.52-approximation algorithm by Mahdian, Ye and Zhang.

Moreover, it cuts the gap with the approximability lower bound by 1/3.

An algorithm is a (λ_f,λ_c)-approximation algorithm if the solution it produces has total cost at most λ_f · F* + λ_c · C*, where F* and C* are the facility and the connection cost of an optimal solution.

Our new algorithm, which is a modification of the (1+2/e)-approximation algorithm of Chudak and Shmoys, is a (1.6774,1.3738)-approximation algorithm for the UFL problem and is the first one that touches the approximability limit curve (Γ_f, 1+2e^(-Γ_f)) established by Jain et al.

As a consequence, we obtain the first optimal approximation algorithm for instances dominated by connection costs. When combined with a (1.11,1.7764)-approximation algorithm proposed by Jain, Mahdian and Saberi, and later analyzed by Mahdian, Ye and Zhang, we obtain the overall approximation guarantee of 1.5 for the metric UFL problem.

We also use our algorithm to improve the approximation ratio for the 3-level version of UFL.

July 9, 2008, 14:15h – MA12

José R. Correa, Universidad de Chile, Chile, “Pricing with markups in congested markets”

We study a game that models a market in which heterogeneous producers make pricing decisions in a first stage, followed by consumers that select a producer selling at lowest price. Producers submit a price function to the market, which maps a production level to a price. Solutions of this type of models are normally referred to as supply function equilibria, and the most common application is in electricity markets. In our model, producers have increasing marginal production costs equal to a linear function, and adopt price functions that are proportional to their production costs. Therefore, the decision in the first phase of the game is the markup producers apply to the production cost. In a second phase of the game, consumers learn the producers’ price functions, which leads to an allocation of consumers to producers.
We prove that an equilibrium exists if and only if there are at least three producers, and if an equilibrium exists, it is unique. We also establish that for highly competitive markets, the equilibrium assignment is nearly efficient, where an efficient assignment is one that minimizes the total production cost. Furthermore, we establish an almost tight bound on the worstcase inefficiency of an equilibrium. In particular, the bound states that when there are two equally efficient producers and possibly other less efficient ones, the production cost under an equilibrium is at most 50% worse than the optimal one, and the worst-case gap between the two assignments decreases rapidly as competition increases. For instance, for three similarly-efficient producers plus perhaps other less efficient ones, the inefficiency is below 6.2%.
This is joint work with Nicolas Stier-Moses.

July 2, 2008, 14:15h – MA 12

Christian Ikenmeyer, University of Paderborn, Germany, “A combinatorial polynomial time algorithm for deciding the positivity of Littlewood Richardson coefficients”

Littlewood-Richardson coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the general linear group GL_n(C). The coefficients have a wide variety of interpretations in combinatorics, representation theory, geometry, and in the theory of symmetric functions. It is known that the problem of computing Littlewood-Richardson coefficients is #P-complete. Quite surprisingly, as first pointed out by Mulmuley and Sohoni, it is possible to decide the positivity of Littlewood-Richardson coefficients in polynomial time. This follows by combining Knutson and Tao’s proof of the Saturation Conjecture (1999) with the fact that linear optimization is solvable in polynomial time. We present an explicit *combinatorial* polynomial time algorithm for deciding the positivity of Littlewood-Richardson coefficients. This algorithm is highly adapted to the problem and uses ideas from the theory of optimizing flows in networks.

June 18, 2008, 14:15h – MA12

Sören Laue, MPI Saarbrücken, Germany, “Set Cover and Hitting Sets for Polytopes in R³“

Suppose we are given a finite set of points P in R³ and a collection of polytopes that are all translates of the same polytope T. I will consider two problems in this talk.

The first is the set cover problem where we want to select a minimal number of polytopes from the given collection such that their union covers all input points P. The second problem that we consider is finding a hitting set for the set of polytopes, that is, we want to select a minimal number of points from the input points P such that every given polytope is hit by at least one point.

I will give the first constant-factor approximation algorithms for both problems. The result is achieved by providing an epsilon-net for translates of a polytope in R³ of size O(1/ε) which is tight up to a multiplicative constant. This extends the constant-factor approximation algorithm for the set cover problem for unit cubes by Clarkson and Varadarajan.

The talk is based on the paper: S. Laue. Geometric Set Cover and Hitting Sets for Polytopes in R³. STACS 2008,

May 7, 2008, 14:15h – MA 12

Thomas Rothvoss, EPFL, Switzerland, “Real-Time Scheduling and Directed Diophantine Approximation”

We present present a relation between a directed version of the well-known problem to simultaneously approximate n rational numbers and the uniprocessor scheduling problem.