Advanced Course on Combinatorial Geometry and Optimization

This is a joint seminar of the Discrete Optimization Group and the Combinatorial Geometry Group.

11.04.2013, 14h

Lilli Bergner: Multi-level LPs and Sigma-2 Completeness

Abstract:
In my master project, I study the complexity of the integrality gap problem of bin packing from a theoretic and algorithmic point of view. This is a prominent question in the field of integer linear programming that asks whether the integrality gap of the Gilmore-Gomory formulation of the bin packing problem is bounded by a constant. A $O(\log^2 n)$ upper bound was proved by Karmarkar and Karp 30 years ago, however, numerous experiments suggest that the gap is smaller than 2.
In the presentation, I will briefly introduce this problem and conjecture its $\Sigma_2^P$-completeness by formulating it as a multi-level integer program. Finally, I will explain the general approach on how to prove complexity results in the second level of the polynomial time hierarchy.

18.03.2013, 11h

Ralf Wimmer (Albert-Ludwigs-University Freiburg), “SMT solver”

14.03.2013, 13h

Alfonso Cevallos, “Classification of graphs with odd cycle packing number 1”

Based on this paper.

06.03.2013, 14h

Carsten Moldenhauer, “Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems.”

Based on this paper.

15.02.2013, 11h

Yuri Faenza, “Razborov’s disjointness lemma and its consequences for linear programming“

23.01.2013

Gautier Stauffer, “Minimum weighted clique-cover in claw-free perfect graphs and the weak Edmonds-Johnson property“

Laura Sanità, “0-1 polytopes with quadratic Chvátal rank“

20.12.2011, 15h15 – MA B1 524 (TTX)

Gabriel Nivasch, “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.

20.12.2011, 14h00 – MA B1 524 (TTX)

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.

13.12.2011, 14h00 – MA B1 524 (TTX)

Carsten Moldenhauer, “Inapproximability of Single-source Rent-or-Buy”

06.12.2011, 14h00 – MA B1 524 (TTX)

Radoslav Fulek, “Recent progress on crossing numbers”

29.11.2011, 14h00 – MA B1 524 (TTX)

Martin Niemeier, “Sampling methods for SVP and friends”

Given a basis B of the n-dimensional euclidean vector space, the lattice generated by B is the set of integer linear combinations of vectors from B. We consider three fundamental problems associated to lattices:
– Shortest vector problem (SVP): Find a shortest nonzero lattice vector
– Closest vector problem (CVP): Given a vector t from the space, find a lattice vector that is closest to t
– Subspace avoiding problem (SAP): Given a subspace M, find the shortest lattice vector not contained in M
We study the “classical” randomized singly exponential time (2^O(n)) algorithm by Ajtai, Kumar and Sivakumar (2001) to solve SVP.  Moreover we discuss an extension by Bloemer and Naewe (2007) to (1+eps)-approximate SAP and CVP in time (1/eps)^O(n)

22.11.2011, 14h00 – MA B1 524 (TTX)

Slobodan Mitrovic, “Disjoint homometric sets on graphs”

For a given graph H by Profile(H) we are going to denote multiset of distances between all the pairs of vertices in H.
The main question in these lectures will be the following: for disjoint subgraphs A and B of a graph G, what is the maximal/minimal size of |A| such that Profile(A) = Profile(B).

For the first time the question whether two Profiles are the same or not was considered on finite sets of integers. Later, the same question appeared in music referring to order of notes.
Lately people are trying to show certain properties on graphs in general, and on some special structures like graphs with small diameters and trees.

In these lectures we are going to present how this problem evolved during the history, and to present some fresh results (Follow-up lecture on Wednesday, November 23, 14h00).

15.11.2011, 14h00 – MA B1 524 (TTX)

08.11.2011, 14h00 – MA B1 524 (TTX)

Geza Toth (Renyi Institute), “Degenerate thrackles”

01.11.2011, 14h00 – MA B1 524 (TTX)

Nicolai Hähnle, “Null- and Positivstellensatz: Transfer Principles, Decision Methods, and Certificates”

We consider three different questions about systems S(x) of equations and inequalities.

1. Suppose S(x) has a solution over a field F_1. Can we conclude that S(x) also has a solution over a related field F_2?
2. How can we decide satisfiability?
3. If S(x) is unsatisfiable, can we find a short certificate for this fact?

We will explore the tight relationship between those questions in the context of the Nullstellensatz and the Positivstellensatz. In particular, we will give a proof of the Nullstellensatz. Proofs for the somewhat more complicated context of the Positivstellensatz will most likely have to be postponed for a later seminar.

20.10.2011, 13h30 – MA B1 524 (TTX)

Guy Even, “Linear-Programming Decoding of Error Correcting Codes” (3)

-Lower bounds for the probability that the transmitted codeword is locally optimal
-An iterative decoding algorithm
-Iterative decoder finds a locally optimal codeword if one exists
-Discussion of extensions and open problems

18.10.2011, 15h00 – MA A1 10

Guy Even, “Linear-Programming Decoding of Error Correcting Codes”  (2)

-Definition of locally optimal codewords
-Local optimality is a sufficient condition for successful Maximum Likelihood decoding
-Local optimality is a sufficient condition for successful LP-decoding

17.10.2011, 14h00 – MA B1 524 (TTX)

Guy Even, “Linear-Programming Decoding of Error Correcting Codes”

-Brief explanation of communication over noisy channels and error correcting codes
-Definition of Maximum Likelihood decoding
-Representation of error correcting codes using Tanner graphs
-Definition of Linear-Programming (LP) decoding
-Characterization of LP-decoding using graph cover decoding
-Symmetry properties of LP-decoding

References

Feldman, Wainwright, and Karger.  Using linear programming to decode binary linear codes. IEEE-IT 2005.
Vontobel and Koetter. Graph-cover decoding and finite length analysis of message-passing iterative decoding of LDPC codes. Arxiv 2005.
Arora, Daskalakis, and Steurer. Message passing algorithms and improved LP decoding. STOC 2009.
Even and Halabi. On decoding irregular Tanner codes. Arxiv 2011.

11.10.2011, 14h00 – MA B1 524 (TTX)

Filip Moric, “Erdős’ Distinct Distance Problem”

More than sixty-five years ago Erdős raised the following  question:  at least how many distinct distances must occur among N  points in the plane? A couple of months ago L. Guth and N. H. Katz almost completely proved Erdős’ conjecture, using a mix of algebraic and geometric techniques.

This is the first of three lectures. The series continues on Wednesday, October 12 at 16h00 and on Thursday, October 13, at 14h00.

Poster

13.09.2011, 11h00 – MA B1 524 (TTX)

Hassan Hijazi, “Some nonlinear optimization theory in integer programming”.

We will expose a simple case study about modeling disjunctive constraints featuring unbounded variables using nonlinear optimization tools. We will talk about convex and invex formulations and their influence in integer programming theory.

26.08.2011, 14h00 – MA B1 524 (TTX)

David Pritchard, “Counting Large Distances in Convex Polygons: A Computational Approach”

In a convex n-gon, let d1 > d2 > … denote the set of all distances between pairs of vertices, and let mi be the number of pairs of vertices at distance di from one another. Erdős, Lovász, and Vesztergombi conjectured that m1+…+mk ≤ kn. Using a new computational approach, we prove their conjecture when k ≤ 4 and n is large; we also make some progress for arbitrary k by proving that m1+…+mk ≤ (2k-1)n. Our main approach revolves around a few known facts about distances, together with a computer program that searches all small configurations of distances generated by two disjoint intervals. We thereby obtain other new bounds such as m3 ≤ 3n/2 for large n.

This is joined work with Filip Moric, published at EuroComb ’11.

22.08.2011, 14h00 – MA B1 524 (TTX)

Carsten Moldenhauer, “Single-Source Rent-or-Buy problem”

Mostly, we will discuss the primal-dual approach (LP!) of the following paper.

References

C. Swamy and A. Kumar: Primal-Dual Algorithms for Connected Facility Location Problems, Algorithmica 40(4):245–269, 2004. [DOI]

04.08.2011, 14h00 – MA B1 524 (TTX)

Martin Niemeier, “ Memory constrained scheduling ”

We address new challenges arising in task schedulers for modern multiprocessor architectures and real-time systems. In addition to “classical” makespan minimzation scheduling on parallel processors, an “orthogonal” constraint has to be taken into account: Tasks come with an additional resource requirement (e.g. memory). A feasible schedule must ensure that for any set of tasks that is simultaneously active on different processors, their total resource requirement does not exceed a certain limit.
After giving a short overview over preliminary results, I will present a polynomial time approximation scheme for makespan minimization on identical parallel machines with shared memory constraints, if the number of different memory requirements if constant.

02.08.2011, 14h00 – MA B1 524 (TTX)

Madalina Hodorog, “ Approximate algorithms for plane curve singularities ”

Recently, algebraic curves and surfaces play an increasing role in applications domains such as computer aided geometric design, computer vision, robotics, etc. For this reason, theoretical results have to be adapted to practical needs. We thus need efficient algorithms for representing, manipulating, analyzing and rendering algebraic curves and surfaces. In this talk, we approach the algebraic problem of computing local invariants of a plane complex algebraic curve defined by a polynomial with inexactly-known coefficients. Hence, we deal with an ill-posed problem in the sense that, tiny changes in the input data lead to huge modifications in the output solution.
We present a regularization method for handling the ill-posedness of the problem. We first design approximate algorithms to extract structural information on the plane complex algebraic curve: (1) we compute the link of each singularity by numerical equation solving; (2) we compute the Alexander polynomial of each link by using algorithms from computational geometry and combinatorial objects from knot theory; (3) we derive formulas for the local invariants. We then prove the convergence for inexact data of the approximate algorithms. Moreover, we perform several numerical experiments, which support the validity for the convergence statement.
We implement the algorithms in the Axel free algebraic geometric modeler and in the Mathemagix free computer algebra system. Both of these free systems are developed at INRIA Sophia-Antipolis and for our purpose they provide algebraic and geometric tools for manipulating both exact and inexact input data.

22.07.2011, 14h00 – MA B1 524 (TTX)

Rico Zenklusen, “ Recent Advances in Submodular Function Maximization ”

Due to their property of diminishing returns, submodular functions naturally appear in many optimization problems, and considerable interest arose in the question how to maximize them under various side constraints. During this talk, I plan to first give a rather general introduction to submodular function optimization, and present some of the main ideas and techniques used in state-of-the-art methods to approximately maximize submodular functions. If time permits, I will discuss in more detail some recent work with Chandra Chekuri and Jan Vondrák on a general framework to approximately maximize submodular functions under various packing constraints.

21.07.2011, 14h00 – MA B1 524 (TTX)

Neil Olver, “ A generalization of the VPN Conjecture ”

Consider the problem of setting up a virtual private network (VPN) for a company, by reserving bandwidth on an existing underlying network. This we would like to do as cheaply as possible, while ensuring we reserve enough capacity to meet the company’s needs. A complication is that the demand pattern across the VPN – which terminals in the network are communicating with which others, and how much bandwidth they need – is not fixed, but uncertain and changing with time. Robust network design is an approach to this difficulty; a *set* of possible demand patterns is specified, and we must ensure there is enough capacity to route any demand in this uncertainty set.
Different choices of this uncertainty set yield different problems. The “hose model” is a case that has been quite well studied, and the optimization problem turns out to be polynomially solvable. I will talk about a generalization of this hose model (that I think is quite natural), which I optimistically conjecture is also polynomial.

19.07.2011, 14h00 – MA B1 524 (TTX)

Ola Svensson, “ Approximating Graphic TSP by Matchings ”

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost.
For the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework allows for generalizations in a natural way and also leads to a 1.586-approximation algorithm for the traveling salesman path problem on graphic metrics where the start and end vertices are prespecified.
Joint work with Tobias Mömke.

18.07.2011, 14h30 – MA B1 524 (TTX)

Marco Di Summa, “ Tree metric and ultrametric approximation of distance functions ”

I will discuss the problem of approximating a given distance function by a tree metric or an ultrametric (i.e., a tree metric in which all root-leaf distances have the same value). I will present some known results, in particular a simple exact algorithm (resp., 3-approximation) for the problem of finding the ultrametric (resp., tree metric) minimizing the maximum additive distortion of an edge. I will also discuss some open problems.

15.07.2011, 14h00 – MA B1 524 (TTX)

David Pritchard, “ Adding partition-matroid constraints to packing problems ”

Let Ax <= 1 be an integer program, where A is 0-1; let B be a 0-1 matrix with one 1 per column. Suppose finding an approximately optimal 0-1 x subject to Ax <= 1 is easy; is it still easy under the additional constraint Bx <= 1? In a few specific cases, the answer is “yes,” via the “fractional local ratio” technique. The main part of the talk will be a description of this technique.

13-14.07.2011, 14h00 – MA B1 524 (TTX)

Thomas Rothvoss, “ The Group Steiner Tree problem ”

I would like to talk about a O(log^3 n)-apx for Group Steiner Tree and a 2^O(sqrt{\log n})-apx for a generalization from this paper.

12.07.2011, 14h00 – MA B1 524 (TTX)

Nicolai Hähnle, “ The Lovasz-Simonovits isoperimetric inequality ”

Suppose you partition a convex body into two measurable sets. Can you give a lower bound on their common surface? This question has applications in expansion properties of graphs with a geometric representation.
If the common surface is sufficiently “nice” (rectifiable), then a nice answer is given by an isoperimetric inequality due to Lovasz and Simonovits, based on earlier work of Dyer and Frieze and of Applegate and Kannan.

31.05.2011, 14h00 – MA B1 524 (TTX)

Andres J. Ruiz-Vargas, “ Beck-Fiala and beyond ”

We’ll study combinatorial discrepancy of sets systems. Mainly, we will prove Beck-Fiala’s famous theorem on the discrepancy of sets systems with bounded degree; and we will sketch the proof of a theorem by Spencer on the discrepancy of sets systems where the number of vertices is the same as the number of sets.

References: “Ten lectures on the Probabilistic method” by J. Spencer.

24.05.2011, 14h00 – MA B1 524 (TTX)

Filip Moric, “ Approximation of a Convex Body by Polytopes ”

We’ll talk about a well-known result: in order to obtain a decent approximation of an n-dimensional ball by a polytope, many vertices (in terms of n) will be necessary.

References: based on corresponding chapters of Pach’s “Combinatorial Geometry” and Matousek’s “Lectures on Discrete Geometry”.

17.05.2011, 14h00 – MA B1 524 (TTX)

David Pritchard, “ Some 0/1 polytopes need exponential size extended formulations ”

A polyhedron with exponentially many facets can sometimes be written in a smaller form by describing it in a higher dimension with extra variables, and then projecting back down to the original space — this can be done for many well-studied LPs to give a polynomial-size description. The main result is that for the TSP polytope, no polynomial-size extended formulation exists (unless NP has poly-size nonuniform circuits). The methods extend Yannakakis’ characterization of extension complexity. Along the way, we also get the new result comprising the title of the paper.

Reference: “Some 0/1 polytopes need exponential size extended formulations” by Thomas Rothvoss http://arxiv.org/abs/1105.0036

12.04.2011, 14h00 – MA B1 524 (TTX)

Nabil Mustafa, “The planar-graph separator theorem and its applications”

The planar graph separator theorem is one of the most useful techniques for deriving approximation algorithms for various geometric packing/hitting-set problems. In this talk I present a simple proof for a PTAS for independent sets of fat objects in the plane.

From “Polynomial-Time Approximation Schemes for Packing and Piercing Fat Objects” by T. Chan.

07.04.2011, 14h00 – MA B1 524 (TTX)

Laura Sanità, “Well-separated pairs decomposition for doubling metrics”

The doubling dimension of a metric is the smallest k such that any ball of radius 2r can be covered using 2^k balls of radius r. I will explain how to compute efficient well-separated pairs decompositions for metrics with constant doubling dimension. The result is from a paper of Talwar (STOC ‘04).

05.04.2011, 14h00 – MA B1 524 (TTX)

Nicolai Hähnle, “Unimodular covers of cones and polytopes”

Given a rational simplicial cone C = cone { v_1, …, v_d }, there exists a finite collection of unimodular cones in C whose union covers C. The surprising result is that one can restrict the unimodular cones such that their generators are all contained in c_d * conv { 0, v_1, …, v_d }, where c_d is polynomial in the dimension and independent of the complexity of C. A closely related result is that there is a constant c’_d, depending only on the dimension, such that kP has a unimodular cover for every integer k > c’_d and lattice polytope P.

22.03.2011, 14h00 – MA B1 524 (TTX)

Carsten Moldenhauer, “Primal-Dual Approximation Algorithms for Node-Weighted Steiner Tree on Planar Graphs”

Node-Weighted Steiner Tree is the following problem: Given an undirected graph, a set of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects all terminals. We consider the restriction to planar graphs. Recent work on this problem has shown that the generic primal-dual algorithm of Goemans and Williamson yields a 3-approximation and that the factor of three is best possible for the algorithm. In this talk, I will present the algorithm, proof ideas, a worst case example and outline some further conclusions.

08.03.2011, 14h00 – MA B1 524 (TTX)

David Pritchard, “Iterative packing for demand matching and sparse packing”

The main result we will present is a 2k-approximation algorithm for the following “k-hypergraph demand matching” problem: given a set system with sets of size <=k, where sets have profits & demands and vertices have capacities, find a max-profit subsystem whose demands do not exceed the capacities. The main tool is an iterative way to explicitly build a decomposition of the fractional optimum as 2k times a convex combination of integral solutions. If time permits we’ll also show how the approach can be extended to a 3-approximation for 2-column sparse packing. The second result is tight w.r.t the integrality gap, and the first is near-tight as a gap lower bound of 2(k-1+1/k) is known.

Paper: Iterative packing for demand matching and sparse packing, Ojas Parekh, IPCO 2011.

01.03.2011, 14h00 – MA B1 524 (TTX)

Marco Di Summa, “Convex discrete maximization”

This seminar deals with the extremely difficult problem of maximizing a convex function over a discrete set. Following the presentation given by Shmuel Onn in his survey “Convex discrete optimization”, we will see that in fixed dimension (and under a suitable geometric condition) it is possible to reduce any convex discrete maximization problem to strongly polynomially many linear discrete optimization problems over the given feasible region. We will also see that (under the same conditions) when the feasible region is a 0-1 set presented by a membership oracle, a convex discrete maximization problem can be solved in polynomial time.

21.12.2010, 14h30 – MA B1 524 (TTX)

Adrian Bock, “Pareto optimality II”

Following up with the ideas of pareto optimality, we present some results on finding the smallest epsilon-approximate pareto set. Assuming an oracle for the GAP(delta)-problem, there exists for two objectives a way to find an epsilon-approximate pareto set that is at most three times as big as the smallest one. This bound is tight. For d objectives, the problem of finding such a set is (at least) as hard as Set Cover, even if all solution points are given in the input.

Based on: Vassilvitskii, Yannakakis. Efficiently computing succinct trade-off curves. ICALP 2004.

14.12.2010, 14h00 – MA B1 524 (TTX)

Nabil Mustafa, “Geometric Applications of a Randomized Optimization Technique”

One standard way to design an algorithm for an optimization problem is to first consider the decision version of the problem, which is often easier to solve. And then use various forms of binary search and parametric search to derive the optimization algorithm via repeated calls to the decision version. This typically incurs some extra polylogarithmic factor overhead. In this talk, we’ll present a variation due to T. Chan (“Geometric Applications of a Randomized Optimization Technique”) where if the problem satisfies some extra conditions, then one can avoid these overheads.

07.12.2010, 14h00 – MA B1 524 (TTX)

Sebastian Schenker, “Approximating Pareto sets in multi-criteria optimization”

In multi-criteria optimization problems one can usually not expect to find a solution that optimizes all objectives simultaneously. In general, improving one objective will lead to a worsening in another criterion. Therefore, a decision maker will be interested in a solution set that reflects those inherent trade-offs – the so-called Pareto set. Unfortunately, the Pareto set is often huge and cannot be computed efficiently, in general. Hence, the concept of approximation comes into play. After motivating and introducing the notion of approximate Pareto sets, we will talk about some results (coined by Papadimitriou and Yannakakis) that address the issue of existence and computability of approximate Pareto sets.

06.12.2010, 10h00 – MA B1 524 (TTX)

Ola Svensson, “Santa Claus Schedules Jobs on Unrelated Machines”

One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines. More than two decades after its introduction it is still the algorithm of choice even in the restricted model where a job can only be assigned to a given subset of the machines on which it has the same processing time. This problem, also known as the restricted assignment problem, is NP-hard to approximate within a factor less than 1.5 which is also the best known lower bound for the general version.

In this talk, we give an overview of the proof of a polynomial time algorithm that estimates the optimal makespan of the restricted assignment problem within a factor 1.9412. The result is obtained by upper bounding the integrality gap of a certain strong linear program, known as configuration LP, that was previously successfully used for the related Santa Claus problem. Similar to the strongest analysis for that problem our proof is based on a local search algorithm that will eventually find a schedule of the mentioned approximation guarantee, but is not known to converge in polynomial time.

Similar to the Santa Claus problem, our result raises the open question whether there is an efficient rounding of the configuration LP that matches the bound on the integrality gap. Another interesting direction that I would like to discuss is to improve the upper or lower bound on the integrality gap.

16.11.2010, 14h00 – MA B1 524 (TTX)

David Pritchard, “Approximately Counting Knapsack Solutions Deterministically”

The problem of counting the number of feasible solutions to a knapsack problem is #P-hard, but a randomized fully polynomial-time approximation scheme was found in 1993 by Dyer and coauthors. Recently, two groups of authors found there is a *deterministic* fully polynomial-time approximation scheme. As a bonus, these algorithms also reduce the time complexity dependence on 1/epsilon from quadratic to linear. I’ll mainly talk about the paper of Stefankovic, Vempala, and Vigoda since it is easy to explain, and as time permits I will touch on the other paper of Gopalan, Klivans and Meka.

09.11.2010, 14h00 – MA B1 524 (TTX)

Nicolas Bonifas, “The Generalized Basis Reduction Algorithm”

I will present the Lovász-Scarf basis reduction algorithm, which is a Lenstra-like algorithm for solving integer programming in polynomial time in fixed dimensions. This method avoids the ellipsoidal approximations required in Lenstra’s algorithm, and might be of practical use. I will also discuss one of the early implementation of this method.

This talk will be based on the papers:
L. Lovász and H.E. Scarf, The Generalized Basis Reduction Algorithm, Mathematics of Operations Research, 1992.
W. Cook, T. Rutherford, H.E. Scarf and D. Shallcross, An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming, ORSA Journal on Computing, 1993.

02.11.2010, 14h00 – MA B1 524 (TTX)

Nathalie Pellet, “Randomized Weighted Majority versus Spare greedy for convex optimization”

I’ll present two simple approximation algorithms for convex optimization problems, namely the Randomized Weighted Majority algorithm and a variation of sparse greedy algorithm, than run in O(1/delta^2) and O(1/delta) respectively.

Papers:
S. Arora, E. Hazan and S. Kale, The Multiplicative Weights Update Method: a Meta Algorithm and Applications, Manuscript,2005.
K. L. Clarkson, Coresets, Sparse Greedy Approximation, and the Frank-Wolfe Algorithm, in SODA 08: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008.

19.10.2010, 15h00 – MA B1 524 (TTX)

Laura Sanità, “Approximate formulations for the knapsack problem”

I will talk about a result of Bienstock (2008), which shows that for each 0 < epsilon <=1 there exists an extended formulation for the knapsack problem, of size polynomial in the number of variables, whose value is at most (1 + epsilon) times the value of the integer program.
 

12.10.2010, 15h00 – MA B1 524 (TTX)

Thomas Rothvoss, “Balancing vectors”

We present a result of Banaszczyk that says the following: Give me any set of vectors of length <= 1/5 and any convex set K that has gaussian measure at least 1/2. Then there are always signs +/- 1 such that the sum of the vectors lies in K.

Paper: Wojciech Banaszczyk, Balancing vectors and Gaussian Measures of n-Dimensional Convex Bodies
 

05.10.2010, 15h00 – MA B1 524 (TTX)

Nicolai Hähnle, “Extended formulations and non-negative rank”

Given a linear program with exponentially many inequalities, can we find an extended formulation with additional variables but significantly fewer inequalities? I will explain a relation between this question and the non- negative rank of the slack matrix of a polytope, based on the paper: Mihalis Yannakakis, Expressing Combinatorial Optimization Problems by Linear Programs, Journal of Computer and System Sciences 43, pp. 441-466 (1991)
 

28.09.2010, 15h00 – MA B1 524 (TTX)

Luca Furrer, “A two-processor scheduling using maximal matchings”

We present a theorem on matchings by Fujii, Kasami and Ninomiya and show how it can be used to obtain an optimal scheduling for a two-processor scheduling problem with fixed execution times. Futher we discuss possible extensions of the algorithm.
 

01.09.2010, 14h00 – MA B1 524 (TTX)

Rico Zenklusen, “Approximation Schemes for Multi-Budgeted Independence Systems”

A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Some classical optimization problems, such as maximum spanning tree and forest, shortest path, (perfect) matching, independent set (basis) in a matroid or in the intersection of two matroids, become NP-hard even with one budget constraint. Still, for most of these problems efficient deterministic and randomized approximation schemes are known. For two or more budgets, typically only multi-criteria approximation schemes are available, which return slightly infeasible solutions. Not much is known however for strict budget constraints: the goal of this talk is to fill this gap for several of the above-mentioned problems.

It is not hard to see that the above-mentioned problems whose solution sets do not correspond to independence systems are inapproximable already for two budget constraints. For the remaining problems, we present approximation schemes for a constant number k of budget constraints using a variety of techniques: i) we present a simple and widely applicable mechanism to transform multi-criteria approximation schemes into pure approximation schemes. This leads to deterministic and randomized approximation schemes for various of the above-mentioned problems; ii) we show that points in low-dimensional faces of any matroid polytope are almost integral, an interesting result on its own. Exploiting this fact, we obtain a deterministic approximation scheme for k-budgeted matroid independent set; iii) we present a deterministic approximation scheme for 2-budgeted matching. The backbone of this result is a purely topological property of curves in R^2.

This is joint work with Fabrizio Grandoni.
 

13.07.2010, 14h00 – MA A1 12 (TTX)

Naonori Kakimura, “Solving Linear Programs from Sign Patterns”

This talk presents an attempt to connect combinatorial matrix theory with linear programming.
A linear program max{cx | Ax=b, x>=0} is said to be sign-solvable if the set of sign patterns of the optimal solutions is uniquely determined by the sign patterns of A, b, and c. Checking the sign-solvability of a given linear program turns out to be co-NP-complete. We then introduce a class of sign-solvable linear programs in terms of totally sign-nonsingular matrices, which can be recognized in polynomial time. For a linear program in this class, we devise an efficient combinatorial algorithm to obtain the sign pattern of an optimal solution from the sign patterns of A, b, and c. In addition, I will talk a recent related result in matching theory if I have time.

This is a joint work with Satoru Iwata.
 

15.06.2010, 14h00 – MA B1 524 (TTX)

Nicolai Hähnle, “Fourier transforms and transference bounds”

In 1993, Banaszczyk proved a result relating the length of the shortest vector of a lattice with the covering radius of the lattice’s dual. These so called transference bounds are useful e.g. to quickly derive the flatness theorem for ellipsoids (and then, by approximation, for general convex bodies). The proof of the transference bound by Banaszcyk heavily uses Fourier analysis. Following lecture notes by Oded Regev, I will review material on Fourier transforms and explain the proof of a bound that is slightly (by a constant factor) weaker than Banaszcyk’s bound.
 

01.06.2010, 14h00 – MA B1 524 (TTX)

Adrian Bock, “Excess and Orienteering”

– (2 + \eps)-approximation for the minimum excess path problem: Given a metric graph on n vertices, specified nodes s and t and a number k, find a path from s to t visiting at least k vertices and minimizing the difference of the path length and the shortest distance between s and t.
– Derive a 3-approximation for the orienteering problem: Given a metric graph on n vertices, specified nodes s and t and a number D, find a path of length at most D visiting as many vertices as possible.
 

25.05.2010, 14h00 – MA B1 524 (TTX)

Masoud Alipour, “SDP relaxation hierarchies of integer programs”

18.05.2010, 14h00 – MA B1 524 (TTX)

Filip Moric, “Second smallest distances in the plane”

We present a result of P. Brass that the maximum number of second smallest distances among n points in the plane is 24/7n-O(\sqrt n), which is tight. The proof involves solving a linear program on a polyhedron in R^40.
 

11.05.2010, 14h00 – MA B1 524 (TTX)

Friedrich Eisenbrand, “The k-MST problem”

04.05.2010, 14h00 – MA B1 524 (TTX)

Saurabh Ray, “A new proof of density Hales-Jewett theorem”

The Density Hales-Jewett (DHJ) theorem states that for any 0< \delta < 1 and integer k > 0, there is a large enough n such that any subset of {1,2,…,k}^n containing at least a \delta fraction of the elements also contains a “combinatorial line”. This fundamental result in Ramsey theory was proved by Furstenberg and Katznelson in 1991 using sophisticated ergodic techniques. Very recently, a new elementary proof came out as a result of massive “open-source” collaboration of mathematicians on Timothy Gowers’ weblog. The new proof also gives quantitative bounds and Janos has already talked about an application of such bounds in proving lower bounds on the size of Epsilon nets for lines in the plane. I will try to present some of the ideas and connections involved in this proof. The content will be from this paper.
Unfortunately, since the paper is quite long, I will be forced to skip some of the details, which I plan to present in a future talk.
 

27.04.2010, 14h00 – MA B1 524 (TTX)

David Pritchard, “Exact Covers via Determinants”

I will talk about Exact Covers via Determinants.
The paper deals with k-uniform hypergraphs, i.e. set systems with all sets of size k. Let V denote the ground set and n=|V|. One main result is a faster (exponential-time) algorithm to determine if there is a perfect matching (cover by |V|/k sets); the other main result is even better time in the important “k-dimensional matching” special case [the ground set |V| is partitioned into k equal-sized “parts”, and each set in the set system intersects each part exactly once (this generalizes matching in bipartite graphs)].
I’ll give all details for the k-dimensional matching algorithm; the running time is roughly 2^(n*(1-2/k)). The main idea is an inclusion-exclusion formula which by itself gives a 2^n-time algorithm, then some algebraic trickery (permanents, determinants, and Pfaffians) gives the extra improvement.
 

20.04.2010, 14h00 – MA B1 524 (TTX)

Dömötör Pàlvölgyi, “Introducion to Enumerative Combinatorics”

How many ways are there to go from the bottom-left corner of an n by m rectangle to the top-right with up and right steps such that the path remains below the diagonal? How many ways can we draw d non-crossing diagonals into a convex n-gon? How many irreducible representations does the symmetric group over n elements have over the complex numbers? These are all typical questions of enumerative combinatorics, all three can be answered with the help of Young-tableaux. I will answer the first two questions using Catalan-numbers and Young-tableaux, which will the main topic of the talk.
 

13.04.2010, 14h00 – MA B1 524 (TTX)

Monaldo Mastrolilli, “Precedence Constrained Single Machine Scheduling”

The talk is devoted to the single machine scheduling  problem to minimize the weighted sum of completion times. I start presenting the solution of a conjecture by Correa & Schulz that implies that the considered scheduling problem is a special case of the minimum weighted vertex cover. It turns out that the vertex cover graph associated with the scheduling problem is exactly the graph of incomparable pairs defined in dimension theory of partial orders. I will explain the implications of this characterization with some possible future research directions.
 

30.03.2010, 14h00 – MA B1 524 (TTX)

Johannes Blömer, “Analysis of Agglomerative Clustering”

The diameter k-clustering problem is the problem of partitioning a finite subset of R^d into k subsets called clusters such that the maximum diameter of the clusters is minimized. One early clustering algorithm that computes a hierarchy of approximate solutions to this problem for all values of k is the agglomerative clustering algorithm with the complete linkage strategy. For decades this algorithm has been widely used by practitioners. However, it is not well studied theoretically. We analyze the agglomerative complete linkage clustering algorithm. Assuming that the dimension d is a constant, we show that for any k the solution computed by this algorithm is an O(log k)-approximation to the diameter k-clustering problem.

This is joint work with D.Kuntze and C. Sohler

23.03.2010, 14h00 – MA B1 524 (TTX)

Andreas Karrenbauer, “A randomized approximation algorithm for packing/covering LPs”

In this talk, I will present a FOCS 2007 paper of   Koufogiannakis and Young about a randomized approximation algorithm to find a primal/dual feasible pair for a packing/covering LP whose objective values are within a factor of (1+eps) for any given positive eps. The running time is O( n + (r+c) log n / eps^2 ) with high probability, where n is the number of non-zeros, r is the number of rows, and c is the number of columns..

16.03.2010, 14h00 – MA B1 524 (TTX)

Janos Pach, “Old news and new oldies on epsilon-nets”

09.03.2010, 14h00 – MA B1 524 (TTX)

Nicolai Hähnle, “Solving the Closest Vector Problem in Deterministic Single Exponential Time”

Micciancio and Voulgaris give a 2^O(n) algorithm to solve the Closest Vector Problem, improving on the previously best known running time of n^O(n). As a consequence of their result, one can also solve the Shortest Vector Problem and other lattice problems in single exponential time deterministically. Previously, only a randomized single exponential time algorithm was known for the Shortest Vector Problem.
This new algorithm solves CVP using preprocessing, specifically by using a clever recursion scheme to compute the Voronoi cell of a lattice.

02.03.2010, 14h00 – MA B1 524 (TTX)

Laura Sanità, “Expander graphs and robust network design”

09.02.2010, 14h00 – MA B1 524 (TTX)

David Pritchard, “Approximate multicommodity min-cut max-flow”

The naive cut condition alone is not strong enough to ensure a feasible flow exists, but for some universal constant c, if the naive cut condition is satisfied by a factor of c*log k, then a feasible flow exists (where k is the number of terminals). I will give the proof of this result, following the 1998 paper by Aumann & Rabani (it also appears in work of Linial, London & Rabinovich). Along the way we use LP duality and prove a generalization of Bourgain’s theorem (n points embed in L1 with O(log n) distortion).

01.02.2010, 14h00 – MA B1 524 (TTX)

Rico Zenklusen, “A poly(log(k))-Approximation for the Group VPN Problem Using Vertex Sparsifiers”

A recent result by Ankur Moitra about vertex sparsifiers (presented at FOCS ’09) shows that given an edge-weighted graph with a set of terminals, there exist a sparsified graph defined only on the terminals, such that the cuts in the sparsified graph have, up to a logarithmic factor in the number of terminals, the same value as the corresponding minimum terminal cuts in the original graph. We show how this result can be exploited to get a poly(log(k))-approximation algorithm for the group VPN problem on k terminals. In particular, when the number of terminals k is considerably smaller than the total number of vertices n, the proposed algorithm has a much stronger approximation guarantee than the currently best approximation algorithm, which guarantees an approximation factor of O(log(n)).

08.12.2009, 14h00 – MA B1 524 (TTX)

Andreas Karrenbauer, “Matroid Intersection”

01.12.2009, 14h00 – MA B1 524 (TTX)

Martin Niemeier, “General dynamic routingwith per-packet delay guarantees of O(Distance + 1/Session Rate)”

We study dynamic routing in a connection-oriented packet-switching network. We consider a network with arbitrary topology on which a set of sessions is defined. For each session i, packets are injected at a rate r(i) to follow a predetermined path of length d(i). Due to limited bandwidth, only one packet at a time may advance on an edge.

We address the problem of scheduling the sessions at each switch (node), so as to minimize worst-case packet delay and queue buildup at the switches. We show the existence of a periodic schedule that achieves a delay bound of O(1/r(i) + d(i)) with only constant-size queues at the switches. This bound is asymptotically optimal for periodic schedules.

24.11.2009, 14h00 – MA B1 524 (TTX)

Filip Moric, Drawing graphs with right angle crossings

We will study the class of graphs that can be drawn in the plane so that the edges are represented by polygonal lines with small number of bends and only right angle crossings are allowed.

References

W. Didimo, P. Eades, G. Liotta, Drawing graphs with right angle crossings, in Proceedings of the 11th International Symposium on Algorithms and Data Structures, pp. 206–217, 2009. [DOI]

E. Di Giacomo, W. Didimo, G. Liotta, H. Meier, Area, curve complexity and crossing resolution of non-planar graph drawings, in Proceedings of 17th International Symposium on Graph Drawing (GD 2009), 2009.

17.11.2009, 14h00 – MA B1 524 (TTX)

Balázs Keszegh, “Online conflict-free coloring for intervals”

We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I.

References

A. Fiat, M. Levy, J. Matouek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, E. Welzl, Online conflict-free coloring for intervals, Proceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 545–554, 2005. [DOI]

10.11.2009, 14h00 – MA B1 524 (TTX)

Masoud Alipour Babaei, “Approximating minimum bounded degree spanning trees to within one of optimal” – ctd.

References

M. Singh and L.C. Lau, Approximating minimum bounded degree spanning trees to within one of optimal, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pp. 661–670, 2007. [DOI]

03.11.2009, 14h00 – MA B1 524 (TTX)

Radoslav Fulek, “Removing independently even crossings”

For any graph G, crossing_number(G) ≤ (independent_odd_crossing_number(G) \choose 2).

References

M. Pelsmajer, M. Schaefer, D. tefankovič, Removing independently even crossings, Graph Drawing, 2009. [PDF]

27.10.2009, 14h00 – MA B1 524 (TTX)

Jarosław Byrka, Thomas Rothvoß, Laura Sanità, “An LP-based (3/2+ε)-approximation for Steiner Tree”

20.10.2009, 14h00 – MA B1 524 (TTX)

Masoud Alipour Babaei, “Approximating minimum bounded degree spanning trees to within one of optimal”

References

M. Singh and L.C. Lau, Approximating minimum bounded degree spanning trees to within one of optimal, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pp. 661–670, 2007. [DOI]

13.10.2009, 14h00 – MA B1 524 (TTX)

Gennady Shmonin, “Asymptotics of the chromatic index for multigraphs”

We consider the Kahn’s proof that the Goldberg–Seymour conjecture for edge-colouring holds asymptotically, i.e., the chromatic index of a multigraph is asymptotically its fractional chromatic index.

References

J. Kahn, Asymptotics of the chromatic index for multigraphs, Journal of Combinatorial Theory, Series B 68(2):233–254. [DOI]

06.10.2009, 14h00 – MA B1 524 (TTX)

Nicolai Hähnle, “Bounds for lattice polytopes containing a fixed number of interior points in a sublattice”

References

J.C. Lagarias and G.M. Ziegler, Bounds for lattice polytopes containing a fixed number of interior points in a sublattice, Canadian Journal of Mathematics 43(5):1022–1035.

29.09.2009, 14h00 – MA B1 524 (TTX)

Jarosław Byrka, “Playing large games using simple strategies”

I will briefly introduce the concept of Nash Equilibria in Bimatrix Games. Then we will quickly go through complexity of computing exact and approximate equilibria. Finally we will discuss a result from the paper, that there always exists an approximate equilibrium with small (i.e. logarithmic) support. This result implies existence of a QPTAS for the problem, which gives hope that a PTAS also exists. Whether there exists a PTAS remains a major open problem in the area of Computational Game Theory.

References

R. J. Lipton, E. Markakis, and A. Metha, Playing large games using simple strategies, in Proceedings of the 4th ACM Conference on Electronic Commerce (EC 2003), pp. 36–41. [DOI]

16.07.2009, 14h00 – MA B1 524 (TTX)

Friedrich Eisenbrand, “Linear programming with violations”

We consider one application from the paper “Geometric applications of a randomized optimization technique” by T. Chan.

07.07.2009, 14h15 – MA B1 524 (TTX)

Martin Niemeier, “Approximation algorithms for precedence-constrainted scheduling on uniformly related machines”

In the precedence-constrainted scheduling problem on uniformly related machines, there are n jobs with processing times and m machines with different speeds. A job with processing time p executed on a machine of speed s takes time p/s to be processed. Further there is a partial order over the jobs defining precendences, i.e. for two comparable jobs, the smaller has to be finished before the larger one can start.

A feasible schedule is an assignment of jobs to machines and timeslots on the processors, such that no precedence constraints are violated and no machine processes more than one job at a time. The scheduling problem is to find a feasible schedule with minimum makespan, i.e. a schedule that minimizes the maximum finishing time of the jobs.

We study an O(log m) approximation algorithm by Chudak and Shmoys (1997), which combines an LP based approach with a variant of Grahams list scheduling algorithm.

23.06.2009, 14h15 – MA B1 524 (TTX)

Thomas Rothvoß, “Unsplittable flows”

We are given an undirected graph G=(V,E) with costs c(e), capacities u(e), a single source s, terminals t_i, demands d_i and a flow f satisfying the demands. A conjecture of Goemans says that there always exists an unsplittable flow f‘ with c(f‘) ≤ c(f) and f‘(e) ≤ f(e) + d_max.

We present an algorithm of Skutella that (1) proves the conjecture if all demands are powers of 2 and (2) computes an unsplittable flow f‘ with c(f‘) ≤ c(f) and f‘(e) ≤ 2 f(e) + d_max in the general case.

02.06.2009, 12h15 – MA B1 524 (TTX)

Dömötör Pálvölgyi, “Combinatorial necklace splitting and Tucker’s lemma”

In the necklace splitting problem, we have an open necklace with k types of beads, a_i beads of the ith kind and p thieves wants to split it by using as few cuts as possible, such that each of them gets ⌊ a_i/p⌋ or ⌈a_i/p⌉ beads of the ith kind. They can cut the necklace between any two beads. If the different types of beads are after each other, then it is easy to see that (p–1)k cuts are necessary. That this number is always enough was proved for p=2 by Goldberg and West. Later Alon and West gave a simpler proof using the Borsuk–Ulam theorem. This was generalized to arbitrary p, each kind having a multiple of p number of beads by Alon. I will present a new, combinatorial proof for the necklace splitting problem for two thieves and a generalization.

26.05.2009, 12h15 – MA B1 524 (TTX)

Laura Sanità, “A primal-dual approximation algorithm for the Steiner forest problem”

In the Steiner forest problem, we are given a undirected weighted network G and k disjoint subsets of terminals. The aim is to find a min-cost subgraph of G where each subset is connected.

We describe a 2-approximation algorithm for the Steiner forest problem based on a primal-dual scheme and a generalization of the approximation technique for constrained forest problems, given by Goemans and Williamson (1995).

References

M.X. Goemans and D.P. Williamson, A general approximation technique for constrained forest problems, SIAM Journal of Computing 24(2): 296–317, 1995. [DOI]

19.05.2009, 12h15 – MA B1 524 (TTX)

Adrian Dumitrescu, “The forest hiding problem: An illumination problem for maximal disk packings”

Let Ω be a disk of radius R in the plane. A set F of closed unit disks contained in Ω forms a maximal packing if the unit disks are pairwise disjoint and the set is maximal: i.e., it is not possible to add another disk to F while maintaining the packing property. A point p is hidden within the “forest” defined by F if any ray with apex p intersects some disk of F: that is, a person standing at p can hide without being seen from outside the forest. We show that if the radius R of Ω is large enough, one can find a hidden point for any maximal packing of unit disks in Ω. This proves a conjecture of Joseph Mitchell.

Joint work with Minghui Jiang.

12.05.2009, 12h15 – MA B1 524 (TTX)

Dömötör Pálvölgyi, “Polychromatic colorings of arbitrary rectangular partitions”

A general (rectangular) partition is a partition of a rectangle into an arbitrary number of non-overlapping subrectangles. In this talk I examine vertex colorings using four colors of general partitions where every subrectangle is required to have all four colors appear on its boundary. It is shown that there exist general partitions that do not admit such a coloring. This answers a question of Dimitrov et al. It is also shown that the problem to determine if a given general partition has such a 4-coloring is NP-Complete. Some generalizations and related questions are also treated. For more info, see this paper

05.05.2009, 12h15 – MA A1 10

Nicolai Hähnle, “The Okamura-Seymour Theorem”

Given a planar graph G = (V, E) and a set of demand pairs (s_i, t_i), the Okamura–Seymour theorem gives sufficient conditions for the existence of edge-disjoint paths P_i between s_i and t_i.

21.04.2009, 12h15 – MA A1 10

Andreas Karrenbauer, “Cycle bases”

I will introduce the problem of computing a shortest cycle basis of a graph. The main result that I will present in this talk is a polynomial-time algorithm exploiting the matroid structure of this problem. Finally, I will discuss open problems.

31.03.2009, 12h15 – MA A1 10

Jarosław Byrka, “On a version of the Set Cover problem”

We consider the problem of covering elements with subsets from a given family of subsets. We are interested in a variant of the problem where each element needs to be covered at least k times and the subsets may be used more then once. We show a greedy algorithm that gives a constant factor approximation in case k = Theta(log n). The constants are slightly better then for the standard randomized LP-rounding algorithm.

This is based on a fragment of my thesis. I will bring enough copies of the thesis to the talk. An electronic version is available in PDF (see last chapter)

24.03.2009, 12h15 – MA A1 10

Paul David Dütting, “Ad auctions, stable matchings, and the Hungarian method”

In an ad auction a certain number of advertisers competes for a limited number of ad slots. Recently, Aggarwal et al. presented a mechanism that generalizes standard auction formats such as VCG and GSP. This mechanism relies on a variant of the Hungarian Method to compute a “stable matching” between advertisers and ad slots. The resulting matching can be shown to be “bidder optimal” and as a consequence each bidder has the incentive to bid “truthfully”.

References

G. Aggarwal, S. Muthukrishnan, D. Pal, M. Pal, General auction mechanism for search advertising, to appear in Proceedings of the 18th International World Wide Web Conference (WWW 2009). [arxiv.org]

17.03.2009, 12h15 – MA B1 524 (TTX)

Laura Sanità, “Approximating arbitrary metrics by tree metrics”

We discuss the problem of approximating a given metric graph by a tree metric, i.e. a metric arising from shortest path distances on a tree containing the given vertices. We describe a result of Fakcharoenphol, Rao and Talwar showing how to probabilistically approximate metric graphs by tree metrics, such that the expected stretch of any edge is O(log n).

References

Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, in Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS 1996), pp. 184–193, 1996. [DOI]

J. Fakcharoenphol, S. Rao, and K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences 69(3):485–497, 2004. [DOI]

10.03.2009, 12h15 – MA B1 524 (TTX)

Friedrich Eisenbrand, “The Lagarias–Odlyzko Algorithm for Subset Sum”

References

A. M. Frieze, On the Lagarias–Odlyzko algorithm for the subset sum problem, SIAM Journal on Computing 15(2):536–539, May 1986. [DOI]

J. C. Lagarias and A. M. Odlyzko, Solving low density subset sum problems, Journal of the ACM 32(1):229–246, January 1985. [DOI]

05.03.2009, 14h15 – MA B1 524 (TTX)

Dömötör Pálvölgyi, “Decision trees and evasive functions”

Link.

23.02.2009, 14h15 – MA B1 524 (TTX)

Radoslav Fulek, “Lower bound on the chromatic number of discrete Borsuk graph”

The continuous version of Borsuk graph is roughly dened on an d-dimensional sphere S^d living in R^d+1 as follows. The set of its vertices is simply the set S^d and two vertices are joined by an edge if they are almost antipodal. We consider a discrete cube-like analogue of Borsuk graph, for which we show a lower and upper bound on its chromatic number. Our bounds depend on a parameter of the graph, which determines at least how far in terms of Hamming distance must be two vertices if they form en edge. While the proof of the upper bound is less involved, the proof of the lower bound relies on topological Borsuk-Ulam theorem. One possible way how to improve our lower bound will be suggested.

05.02.2009, 12h15 – MA B1 524 (TTX)

Nicolai Hähnle, “Independent line segments”

Given n lines segments in R², how can we find a large(st) subset of segments that are pairwise disjoint? This is a special case of the independent set problem in undirected graphs. We describe an approximation algorithm due to Agarwal and Mustafa.

References

P. K. Agarwal and N. H. Mustafa, Independent set of intersection graphs of convex objects in 2D, Computational Geometry 34(2):83–95, 2006. [DOI]

13.11.2008, 14h30 – MA B1 524 (TTX)

Rom Pinchasi, “A solution of a conjecture of Erdős, Purdy and Straus about the minimum number of distinct areas of triangles spanned by a set of n points in the plane”

We prove the following conjecture of Erdős, Purdy, and Straus from 1977: Every set of n points in the plane that is not contained in a line determines at least ⌊(n–1)/2⌋ triangles with pairwise distinct areas. The main tools that will be used are duality between points and lines in the plane and Euler’s celebrated formula V–E+F=2 in the plane.

06.11.2008, 14h30 – MA B1 524 (TTX)

Gennady Shmonin, “Multi-commodity flows, signed graphs and Lehman’s theorem” (contd)

29.10.2008, 14h – MA B1 524 (TTX)

Gennady Shmonin, “Multi-commodity flows, signed graphs and Lehman’s theorem” (contd)

22.10.2008, 14h – MA B1 524 (TTX)

Gennady Shmonin, “Multi-commodity flows, signed graphs and Lehman’s theorem”

Given a graph G=(V,E), a weight function w:E→R₊, and a set of demand edges Σ⊂E, we can think of a multi-commodity flow as a function f:C→R₊, where C is the set of all cycles in G whose intersection with Σ contains exactly one edge. This function f must satisfy the capacity constraints (the total flow through e∉Σ does not exceed w(e)) and the demand constraints (the total flow through e∈Σ is exactly w(e)). The cut-condition (the sum of demands is at most the sum of capacities for every cut in G) is clearly necessary for a flow to exist. We discuss the proof of the Guenin’s theorem: if the cut-condition holds and the signed graph (G,Σ) has no (K₅,EK₅)-minor, then there is a flow in G. The proof exploits the Lehman’s theorem about minimally non-ideal clutters.

References

G. Cornuéjols and B. Guenin, Ideal clutters, Discrete Applied Mathematics 123:303–338, 2002. [DOI]

B. Guenin, A characterization of weakly bipartite graphs, Journal of Combinatorial Theory, Series B 83(1):112–168, 2001. [DOI]

A. Schrijver, A short proof of Guenin’s characterization of weakly bipartite graphs, Journal of Combinatorial Theory, Series B 85(2):255–260, 2002. [DOI]

04.06.2008, 14h – MA 12

Fritz Eisenbrand, “A simply exponential algorithm for shortest vector”

We review the random sampling algorithm of Ajtai, Kumar and Sivakumar, which finds with very high probability the shortest vector in a lattice. The running time of this algorithm is 2^O(n) times a polynomial in the length of the input basis.

References

M. Ajtai, R. Kumar, and D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, in Proceedings of the 33th Annual ACM Symposium on Theory of Computing (STOC 2001) pp. 601–610, 2001. [DOI]

23.04.2008, 14h – MA 12

Gennady Shmonin, “NP-complete decision problems for binary quadratics”

We present the proof of NP-completeness of the following problems: Given non-negative integers a, b, c, (1) decide if there is a solution the two-variable binary quadratics ax² + by – c = 0; (2) decide if there is a non-negative solution x ≤ c of the congruence x ≡ a (mod c). This result has influenced a number of other important NP-completeness proofs, e.g., for diophantine approximation. Another interesting aspect of the above-mentioned problems is that the input consists of just three numbers, while the input to many other NP-complete problems usually involves arrays of numbers.

References

K.L. Manders and L. Adleman, NP-complete decision problems for binary quadratics, ournal of Computer and System Sciences 16(2):168–184, 1978. [DOI]