Algorithmic Meeting
February 11-13, 2013, EPFL, Lausanne


The goal of this workshop is to bring together a number of algorithms researchers from Europe and Israel and to provide a venue that will stimulate establishing their future collaborations. To this end, there will be no focus on any particular topic in algorithms, but rather each participant is asked to give a talk on the direction/problem that she/he is working on currently or would like to pursue in the near future. These talks should be short (30 min.) and rather informal in nature, so as to keep the schedule light-weight and leave plenty of time for informal meetings/discussions.

The workshop is by invitation only.

Confirmed Participants

  • Nikhil Bansal (TU Eindhoven)
  • Marcin Bienkowski (University of Wrocław)
  • Jarosław Byrka (University of Wrocław)
  • Artur Czumaj (University of Warwick)
  • Friedrich Eisenbrand (EPFL)
  • Matthias Englert (University of Warwick)
  • Fabrizio Grandoni (IDSIA)
  • Johan Håstad (KTH)
  • Elad Hazan (Technion)
  • Giuseppe Italiano (Tor Vergata)
  • Robert Krauthgamer (Weizmann)
  • Stefano Leonardi (Sapienza)
  • Aleksander Mądry (EPFL)
  • Kurt Mehlhorn (MPI-I)
  • Marcin Mucha (Warsaw University)
  • Seffi Naor (Technion)
  • Harald Räcke (TU München)
  • Piotr Sankowski (Warsaw University)
  • Christian Sohler (TU Dortmund)
  • Ola Svensson (EPFL)
  • Berthold Vöcking (RWTH Aachen)
  • Peter Widmayer (ETHZ)
  • Gerhard Woeginger (TU Eindhoven)
  • Schedule

    Each talk is scheduled for 30 min. (Standard AV equipment will be available on site.)

    Monday (February 11, 2013)

    10:30 Coffee break
    10:45 Welcome remarks
    11:00 Nikhil Bansal, On Some Online Problems
    I will talk about some online problems which seem like they should be embarrassingly easy, but for which we essentially do not know anything.
    11:35 Elad Hazan, Polynomial Time Convex Optimization without Projections
    What can we optimize in near-linear time? In this talk we discuss an obstacle for efficient large-scale convex optimization - the computation of projections. We then describe the first projection-free polynomial-time algorithm, based on the method of Frank and Wolfe. We'll survey remaining challenges and future research directions for large-scale convex optimization.
    12:10 Fabrizio Grandoni, On Unsplittable Flow
    In the unsplittable flow problem (UF) we are given an undirected graph G with positive edge capacities, and a collection T of source-target pairs (s_i,t_i). Each pair is characterized by a demand d_i and a profit p_i. The goal is to select a subset of pairs T' and a path P_i between s_i and t_i for each (s_i,t_i) in T' so that:
    1) the total profit of T' is maximized and
    2) each pair (s_i,t_i) in T' can simultaneously route a flow of d_i along P_i while respecting edge capacities.
    UF generalizes edge disjoint paths, and it is well studied even in the special case that G is a tree (UFT) or a path (UFP). In this talk we will overview part of the results and techniques in UF literature, with a special focus on UFP.
    12:45 Lunch (Participants on their own)
    14:30 Peter Widmayer, Combinatorial Optimization with Noisy Inputs: How Can We Separate the Wheat From the Chaff?
    Real world data are almost always noisy, and an exact solution to a noisy input of an optimization problem is not what we really want. We propose a way to ignore the noisy part of the given data, while preserving the meaningful part, that is, to separate the information in the data from the noise. We require simply two input instances for this purpose, and we show how to extract the information in these instances. Whenever an instance generator with a strongly peaked distribution hides behind both inputs, our approach shall return a close to optimum solution. We demonstrate the approach at a few simple algorithmic problems, such as finding a minimum in a set of numbers, a maximum subarray, a shortest path in a graph, and a minimum spanning tree. We discuss implications of the approach on the algorithmic complexity of these problems.
    15:05 Christian Sohler, Sublinear Algorithms for the Analysis of Very Large Graphs
    Does the facebook graph of a country reflect its political system? For example, can we distinguish a democratic country from a totalitarian one by looking at their facebook structure?

    To study such questions we need algorithms that "compare" extremely large graphs. Obviously, studying whether the graphs are isomorphic does not solve the problem (and would require way too much time). Instead, we can try to find out, which structural properties the two graphs satisfy. However, this is also often impossible because of the size of the graphs. Therefore, in the area of Property Testing we study the question how to approximately decide by random sampling whether a graph has a certain property or is far away from it. In this talk I will summarize the state of the art in Property Testing for sparse graphs and outline some open problems in the area.
    15:40 Coffee break
    16:10 Seffi Naor, Recent Progress in Maximization of Submodular Functions
    The study of combinatorial problems with submodular objective functions has attracted much attention recently, and is motivated by the principle of economy of scale, prevalent in real world applications. In particular, submodular functions are commonly used as utility functions in Economics and algorithmic game theory. From a theoretical perspective, submodular functions and submodular maximization play a major role in combinatorial optimization, where several well known examples of submodular functions in this setting include cuts in graphs and hypergraphs, rank functions of matroids and covering functions. Several new results along this line of research will be discussed, as well as open problems.
    16:45 Marcin Mucha, No-Wait Flowshop and Asymmetric TSP
    No-Wait Flowshop is a classic problem in schedulling. Despite many years of study its approximability has remained an open problem. Recently, No-Wait Flowshop has received increased attention from the TSP community, as it is a special case of Asymmetric TSP, and as such was perceived as a possible avenue to attacking the general problem.

    In this talk I will introduce the problem and present classic results, as well as new hardness results (joint work with Maxim Sviridenko). I will also discuss the related open problems.

    Tuesday (February 12, 2013)

    9:00 Aleksander Mądry, Can We Make Algorithmic Graph Theory Run in Nearly-linear Time?
    In recent years, the emergence of massive computing tasks that arise in context of web applications and networks has made the need for really efficient, i.e., nearly-linear time, graph algorithms more pressing than ever.

    In this talk, I will discuss some of the questions and problems, as well as, possible directions and tools that I believe to be important for understanding what kind of graph problems can be (approximately) solved in close to linear time.
    9:35 Piotr Sankowski, Algebraic Algorithms for Shortest Undirected Paths, Weighted b-Matching, f-Factors and Much More
    The talk aims to introduce the new algebraic techniques developed for finding weighted f-factors in general graph and much more. Let G=(V,E) be a graph and let f be a function assigning degree bounds for vertices. We propose the first known algebraic algorithms for perfect f-matching and f-factor problems that work in O(f(V)^omega) time, where omega is the matrix multiplication exponent. Next, we consider weighted graphs with integral edge weights of maximum absolute value W. For such graphs we give O(Wf(V)^omega)$ time algorithms for finding maximum weight f-matching and f-factor. This algorithm can be used to solve shortest undirected path problem, weighted b-matching and min-cost max-flow problem.

    However, in the talk, I will actually mention much less and present only the core technique that can be used to solve the max-flow problem in vertex capacitated graphs. I will show an algorithm working in O((Dn)^omega) time, where D is the maximum vertex capacity. I will discuss also the techniques used to solve the weighted version of these problems and relation to shortest undirected paths. I will mention some related open problems.
    10:10 Coffee break
    10:30 Harald Räcke, A New Approach for Constructing Hierarchical Decompositions
    The oblivious schemes of Raecke 02 and Harrelson, Hildrum, Rao 03 rely on approximating the cut-structure of a given undirected graph by a tree. This approximation can be used to derive approximation algorithms for a variety of different problems by solving the problem on a tree instead of having to deal with the full complexity of an undirected graph.

    A major drawback is that the current algorithm for constructing these tree approximations are just polynomial time. This talk presents an approach that may lead to much faster construction algorithms.
    11:05 Gerhard Woeginger, Optimization at the Second Level
    The talk surveys and discusses some algorithmic problems located at the second level of the polynomial hierarchy. The problems are taken from geometry, graph theory, social choice, and robust optimization; some of them are genuinely intractable, and some of them only pretend to be intractable.
    11:40 Marcin Bienkowski, Acknowledgement Aggregation
    In the control message aggregation problem, nodes of a tree send acknowledgements towards the root. These acknowledgements have to be transmitted as soon as possible, however delaying them creates an opportunity of aggregating them into a single message, and thus decreasing the cost of a transmission. I will focus on the online variant, survey state of the art, show relations to production planning problems, and sketch some recent advancements and open problems.
    12:15 Lunch (Participants on their own)
    14:00 Kurt Mehlhorn, Physarum Computations
    (No abstract.)
    14:35 Jarek Byrka, Improved LP-rounding Approximation Algorithm for k-level Uncapacitated Facility Location
    We study the k-level uncapacitated facility location problem, where clients need to be connected with paths crossing open facilities of k types (levels). In this paper we give an approximation algorithm that for any constant k, in polynomial time, delivers solutions of cost at most k times OPT, where k is an increasing function of k, with limk!1 k = 3. Our algorithm rounds a fractional solution to an extended LP formula- tion of the problem. The rounding builds upon the technique of itera- tively rounding fractional solutions on trees (Garg, Konjevod, and Ravi SODA'98) originally used for the group Steiner tree problem. I will also talk about randomizing the scaling parameter in such algorithms and about a prize collecting variant of the problem.
    15:10 Coffee break
    15:40 Berthold Vöcking, Online Algorithms for Combinatorial Auctions
    We present and discuss online algorithms for different variants of combinatorial auctions. Similar to the secretary problem, we assume random arrivals of bidders. The underlying optimization problem might correspond, e.g., to a weighted matching problem in bipartite graphs in which nodes from one side arrive in random order. We are interested in upper and lower bounds on the competitive ratios of online algorithms and discuss issues of incentive compatibility.
    16:15 Stefano Leonardi, Revenue Maximizing Prior-free Auctions with Non-identical Bidders
    Auctions are traditionally evaluated in economics theory using average-case or Bayesian analysis, and expected auction performance is optimized with respect to a prior distribution over inputs. Worst-case guarantees are desirable when, for example, good prior information is expensive or impossible to acquire, and when a single auction is to be re-used several times, in settings with different or not-yet-known input distributions. In this talk, we present prior-free auctions with constant-factor approximation guarantees in both unlimited and limited supply that also apply to a relevant case of non identical bidders. These auctions are simultaneously near-optimal in a wide range of Bayesian multi-unit environments when compared against the performance of Myerson optimal bayesian auction.
    16:50 Matthias Englert, How to Serve Impatient Users
    Consider the following problem of serving impatient users: we are given a set of customers we would like to serve. We can serve at most one customer in each time step (getting value v_i for serving customer i). At the end of each time step, each as-yet-unserved customer i leaves the system independently with probability q_i, never to return. What strategy should we use to serve customers to maximize the expected value collected?

    The standard model of competitive analysis can be applied to this problem: picking the customer with maximum value gives us half the value obtained by the optimal algorithm, and using a vertex weighted online matching algorithm gives us a 1-1/e \approx 0.632 fraction of the optimum. As is usual in competitive analysis, these approximations compare to the best value achievable by an clairvoyant adversary that knows all the coin tosses of the customers. Can we do better?

    (Joint work with Marek Cygan, Anupam Gupta, Marcin Mucha, and Piotr Sankowski)

    Wednesday (February 13, 2013)

    9:00 Johan Håstad, Algorithms and Complexity at KTH, Stockholm
    We briefly describe three research projects ongoing at KTH.

    Approximability of NP-hard optimization problems.

    We study both algorithmic results and hardness results with an emphasis on the latter. One focus of the project has been hardness results for maximum constraint satisfaction problems. Permanent staff within this area is Johan Håstad and Per Austrin.


    Research spans theory and application with the voting software Verificatum as a prime example. Permanent staff Douglas Wikström

    Proof complexity.

    Most work is done on the hardness side studying proof systems that are stronger than resolution. Permanent staff Jakob Nordström.
    9:35 Robert Krauthgamer, Compressing Graphs for Terminal Distances and Cuts
    A key challenge in designing graph algorithms is to compress a graph $G$ so as to preserve some of its basic properties, such as distances and cuts. Both spanners [Peleg and Schaffer, 1989] and cut sparsifiers [Benczur and Karger, 1996] fall into this category, as they reduce the number of edges in $G$ without changing any distance or cut by more than a bounded factor.

    I will discuss another flavor of this challenge, which asks instead to reduce the number of vertices. Specifically, given a graph $G$ and $k$ terminal vertices, we wish to construct a small graph that is a minor of $G$, and in which all the terminal distances equal those in $G$ (exactly). Can we bound the size of $G'$ by some function of $k$? I will also talk about a similar question regarding terminal cuts, called mimicking networks by [Hagerup, Katajainen, Nishimura, and Ragde, 1998].

    Joint works with Inbal Rika and with Tamar Zondiner.
    10:10 Artur Czumaj, Geometric Optimization and Beyond
    After Arora gave a PTAS for geometric TSP, we have seen a flow of results applying and extending Arora's techniques to a variety of geometric optimization problems. Can we still today make any further progress in this area and is there a scope for new ideas and new results?
    10:45 Coffee break
    11:05 Friedrich Eisenbrand, Linear Programming and Diameter of Polyhedra.
    (No abstract.)
    11:40 Giuseppe Italiano, Dynamic Graph Problems
    I will talk about open problems on dynamic graphs (and problems somehow related to dynamic graphs).
    12:15 Ola Svensson, Strong Convex Relaxations for Location Problems
    Facility location is the basic problem where we wish to optimize the placement of facilities to minimize opening costs of facilities and transportation costs of clients. A reasonable and often required constraint is that each facility can accept at most a certain number of clients. Although these so-called capacity constraints look innocent, they have troubled researchers for decades. In fact, the naive linear programming relaxation gives close to optimal guarantees for the facility location problem without capacity constraints, but fails to give any guarantees when capacity constraints are present. Several related problems such as k-median, have the same status, i.e., that there is no known strong relaxation in the case of capacity constraints.

    In this talk, we are going to discuss possible approaches for obtaining stronger relaxations for these problems by the use of hierarchies. We believe that this line of study has the potential to greatly improve our understanding of these problems. In particular, by studying the power of these methods, we were recently able to achieve an approximation guarantee of 1+sqrt(3) for k-median (without capacity constraints) improving upon the decade-old ratio of 3.
    12:50 Workshop adjourns


    All the talks will happen on the EPFL campus in room BC 01 that is located just to the left of the main entrance to the BC building (see the map). To get to building BC from the center of Lausanne, one needs to take the M1 metro train in direction of Renens and exit at the station EPFL (the ride takes about 15 minutes). Next, one needs to take a short walk from the EPFL station as pictured here. The timetable of M1 line to/from EPFL can be checked here. A one-way ride costs 3.50 CHF and one should buy the ticket in a vending machine before boarding the train (more details can be found here).

    Important note: All hotels in Lausanne, upon request, provide a free pass for the Lausanne public transportation that is valid for the duration of your stay (you can use this pass on the M1 line, as well as, on the rest of the extensive bus and metro network).


    There is a large selection of hotels in Lausanne (the easiest way to find a hotel is to use aggregators like Expedia, Hotwire, or Travelocity). As the public transportation in Lausanne is very efficient (and free when one is staying in a hotel - see above), most of the hotels in Lausanne is within reasonable travel distance from the EPFL campus. (Still, making your reservation as soon as possible is highly recommended.)

    Below we describe a few options:
  • (Recommended option) Hotel Ibis Lausanne Center. A hotel in the Lausanne's center - within 5 min. walk of the Vigie M1 metro station. This hotel offers a rebate if one makes reservation at least 30 days in advance and pays upfront.
  • Starling Hotel. A hotel right on the EPFL campus - 6 min. walk from the workshop's venue.
  • Hotel Agora. Another hotel in the Lausanne's center - close to the Lausanne railway station, next to the Grancy M2 metro station (that is within two stops of a transfer to M1 line at Lausanne-Flon station).
  • Organizers

    Artur Czumaj and Aleksander Mądry.