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.
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
| 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
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
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
| 12:15 || Lunch (Participants on their own)|
| 14:00 || Kurt Mehlhorn, Physarum Computations |
| 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
Most work is done on the hardness side
studying proof systems that are stronger
than resolution. Permanent staff
| 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
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.|
| 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
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
, 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).
and Aleksander Mądry