RESEARCH SEMINAR

Submodular functions are set functions that capture the natural "diminishing returns" property and can be seen as a discrete analogy to convex functions. The problem of maximizing a submodular function is as follows: Given a set \(E\) of elements and a set function \(f: 2^E\rightarrow Q\) (typically through an oracle), we want to determine a subset \(S\) of \(E\) with maximum value \(f(S)\). This is an NP-hard problem for which several approximation algorithms are known. These algorithms are either randomized or adaptive, in the sense that they choose which function values to look up after having already seen some others, and in this way adapt to the function. In this talk we discuss a non-adaptive, or oblivious, deterministic approach. All sets for which the value of the function will be queried will be chosen from the beginning as a list. The set of this list with the highest function value will then be returned as an approximation of the problem. The focus of the talk will be choosing such a list and determining the quality of this solution.

This will be a talk covering my general research interests, approximation and online algorithms for scheduling and network design.

First, I will speak about online scheduling problems. We propose a new model on top of the classical competitive analysis that we believe is useful in dealing with uncertainty in the input data. We show that one can design simple online algorithms with good guarantees if one is allowed to reject, that is, not process a tiny fraction of the input. We propose this in the light of the fact that such an algorithm is not possible for optimizing certain classical scheduling objectives like makespan minimization or minimizing the (weighted) maximum flow-time.

Joint work with: Anamitra Roy Choudhury, Naveen Garg and Amit Kumar.

In the second part, I shall talk about network design problems. We give improved approximation guarantees for a classical network design problem called the Group Steiner Tree, when the input graph has a special structure. In particular, we prove a generic reduction of a problem instance on such graphs to a problem instance on trees that allows us to carry out the desired improvement. The reduction may be of independent interest.

Joint work with: Parinya Chalermsook, Bundit Laekhanukit and Daniel Vaz.

Minimizing resource usage is a key to achieving economic, environmental, or societal goals. We consider the fundamental problem of minimizing the number of machines that is necessary for feasibly scheduling preemptive jobs with release dates and hard deadlines. We consider the online variant of this problem in which every job becomes known to the online algorithm only at its release date. We present new competitive algorithms for this problem. We also discuss the power of job migration and show somewhat surprising strong lower bounds on the best possible performance guarantee.

Joint work with: Lin Chen and Kevin Schewior.

Consider the following variant of the set cover problem. We are given a universe \(U=\{1,...,n\}\) and a collection of subsets \(\mathcal{C} = \{S_1,...,S_m\}\) where \(S_i \subseteq U\). For every element \(u \in U\) we need to find a set \(\phi(u) \in \mathcal C\) such that \(u\in \phi(u)\). Once we construct and fix the mapping \(\phi:U \mapsto \mathcal C\) a subset \(X \subseteq U\) of the universe is revealed, and we need to cover all elements from \(X\) with exactly \(\phi(X):=\bigcup_{u\in X} \phi(u)\). The goal is to find a mapping such that the cover \(\phi(X)\) is as cheap as possible. This is an example of a universal problem where the solution has to be created before the actual instance to deal with is revealed. Such problems appear naturally in some settings when we need to optimize under uncertainty and it may be actually too expensive to begin finding a good solution once the input starts being revealed. A rich body of work was devoted to investigate such problems under the regime of worst case analysis, i.e., when we measure how good the solution is by looking at the worst-case ratio: universal solution for a given instance vs optimum solution for the same instance. As the universal solution is significantly more constrained, it is typical that such a worst-case ratio is actually quite big. One way to give a viewpoint on the problem that would be less vulnerable to such extreme worst-cases is to assume that the instance, for which we will have to create a solution, will be drawn randomly from some probability distribution. In this case one wants to minimize the expected value of the ratio: universal solution vs optimum solution. Here the bounds obtained are indeed smaller than when we compare to the worst-case ratio. But even in this case we still compare apples to oranges as no universal solution is able to construct the optimum solution for every possible instance. What if we would compare our approximate universal solution against an optimal universal solution that obeys the same rules as we do? In the talk we will see that under this viewpoint, but still in the stochastic variant, we can indeed obtain better bounds than in the expected ratio model. For the Set Cover problem --- on which the main ideas and characteristics of the model will be presented --- we will see how one can obtain \(H_n\) approximation, which matches the approximation ratio from the classic deterministic setup. Moreover, this result holds for all possible probability distributions over \(U\) that have a polynomially large carrier, while all previous results pertained to a model in which elements were sampled independently. The result is based on rounding a proper configuration IP that captures the optimal universal solution, and using tools from submodular optimization.

Joint work with: Fabrizio Grandoni, Stefano Leonardi and Michał Włodarczyk.

The area of mechanism design is concerned with the development of algorithms that produce good outcomes given inputs from self-interested individuals. Much of mechanism design theory is dominated by the Vickrey-Clarke-Groves (VCG) mechanism, which makes it optimal for each individual to provide its true input. In the real world the VCG mechanism is used with surprising rarity, and some reasons for this are known. We identify another property of the mechanism that may be problematic in practice, a relative lack of robustness to inaccuracies in the choice of its parameters.

Joint work with Paul Dütting and David C. Parkes.