I will talk about some online problems which seem like they should be embarrassingly easy, but for which we essentially do not know anything.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

(No abstract.)

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.

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.

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.

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)

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.

Cryptography.

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.

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.

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?

(No abstract.)

I will talk about open problems on dynamic graphs (and problems somehow related to dynamic graphs).

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.