Accepted Papers
Amariah D. Becker: Capacitated Domination Problems on Planar Graphs
Capacitated Domination generalizes the classic Dominating Set problem by specifying for each vertex a required demand and an available capacity for covering demand in its closed neighborhood. The objective is to find a minimum-size set of vertices that can cover all of the graph’s demand without exceeding any of the capacities. Capacitated r-Domination further generalizes the problem by allowing vertices to cover demand up to a distance r away. In this paper we look specifically at domination problems with hard capacities (i.e. each vertex can appear at most once in the solution). Previous complexity results suggest that this problem cannot be solved (or even closely approximated) efficiently in general graphs. In this paper we present polynomialtime approximation schemes for Capacitated Domination and Capacitated r-Domination in unweighted planar graphs when the maximum capacity is bounded. We also show how this result can be extended to the closely-related Capacitated Vertex Cover problem.
Toshihiro Fujito: On Approximability of Connected Path Vertex Cover
This paper is concerned with approximation complexity of the Connected Path Vertex Cover problem. The problem is a connected variant of the more basic problem of path vertex cover; in k-Path Vertex Cover it is required to compute a minimum vertex set C V in a given undirected graph G = (V;E) such that no path on k vertices remains when all the vertices in C are removed from G. Connected k-Path Vertex Cover (k-CPVC) additionally requires C to induce a connected subgraph of G. Previously, k-CPVC in the unweighted case was known approximable within k2, or within k assuming that the girth of G is at least k, and no approximation results have been reported on the weighted case of general graphs. It will be shown that 1) unweighted k-CPVC is approximable within k without any assumption on graphs, and 2) it is as hard to approximate weighted k-CPVC in general as the weighted set cover, but k-CPVC is approximable within 1:35 ln n + 3 for k 3.
Antonios Antoniadis and Kevin Schewiory: A Tight Lower Bound for Online Convex Optimization with Switching Costs
We investigate online convex optimization with switching costs (OCO; Lin et al., INFOCOM 2011), a natural online problem arising when rightsizing data centers: A server initially located at p0 on the real line is presented with an online sequence of non-negative convex functions f1, f2, …, fn : R → R+. In response to each function fi, the server moves to a new position pi on the real line, resulting in cost |pi – p{i-1}| + fi(pi). The total cost is the sum of costs of all steps. One is interested in designing competitive algorithms.
In this paper, we solve the problem in the classical sense: We give a lower bound of 2 on the competitive ratio of any possibly randomized online algorithm, matching the competitive ratio of previously known deterministic online algorithms (Andrew et al., COLT 2013/arXiv 2015; Bansal et al., APPROX 2015). It was previously conjectured that (2-epsilon)-competitive algorithms exist for some > 0 (Bansal et al., APPROX 2015).
János Balogh, József Békési, György Dósa, Leah Epstein and Asaf Levin: Lower bounds for several online variants of bin packing
We consider several previously studied online variants of bin packing and prove new and improved lower bounds on the asymptotic competitive ratios for them. For that, we use a method of fully adaptive constructions. In particular, we improve the lower bound for the asymptotic competitive ratio of online square packing significantly, raising it from roughly 1:68 to above 1:75.
Boaz Farbstein and Asaf Levin: Deadline TSP
We study the Deadline TSP problem. The input consists of a complete undirected graph G=(V,E), a metric $c:E \rightarrow Z_+$, a reward function $w:V\rightarrow Z_+$, a non-negative deadline function $d:V\rightarrow Z_+$, and a starting node s. A feasible solution is a path starting at s. Given such a path and a node v, we say that the path visits v by its deadline if the length of the prefix of the path starting at s until the first time it traverses v is at most d(v) (in particular, it means that the path traverses v). If a path visits v by its deadline, it gains the reward w(v). The objective is to find a path P starting at s that maximizes the total reward. In our work we present a bi-criteria (1+\eps,\frac{\alpha}{1+\eps})-approximation algorithm for every \eps>0 for the Deadline TSP, where \alpha is the approximation ratio for Deadline TSP with a constant number of deadlines (currently \alpha=1/3 by Chekuri and Kumar) and thus significantly improving the previously best known bi-criteria approximation for that problem (a bi-criteria (1+\eps,\frac{1}{O(\log(1/\eps))})-approximation algorithm for every \eps>0 by Bansal et al.. We also present improved bi-criteria (1+\eps,\frac{1}{1+\eps})-approximation algorithms for the Deadline TSP on weighted trees.
Mário César San Felice, Cristina G. Fernandes and Carla Negri Lintzmayer: The online multicommodity connected facility location problem
Grandoni and Rothvo\ss introduced the Multicommodity Connected Facility Location problem, a generalization of the Connected Facility Location problem which arises from a combination of the Facility Location and the Steiner Forest problems through the rent-or-buy model. We consider the online version of this problem and present a randomized algorithm that is O(log^2 n)-competitive, where n is the number of given client pairs. Our algorithm combines the sample-and-augment framework of Gupta, Kumar, Pál, and Roughgarden with previous algorithms for the Online Prize-Collecting Facility Location and the Online Steiner Forest problems. Also, for the special case of the problem with edge scale factor equals 1, we show that a variant of our algorithm is deterministic and O(log n)-competitive. Finally, we speculate into the possibility of finding a O(log n)-competitive algorithm for the general case and the difficulties to achieve such ratio.
Itay Laish and Shay Mozes: Efficient Dynamic Approximate Distance Oracles for Vertex-Labeled Planar Graphs
Let $G$ be a graph where each vertex is associated with a label. A \emph{Vertex-Labeled Approximate Distance Oracle} is a data structure that, given a vertex $v$ and a label $\lambda$, returns an $(1+\eps)$-approximation of the distance from $v$ to the closest vertex with label $\lambda$ in $G$. Such an oracle is {\em dynamic} if it also supports label changes.
In this paper we present three different dynamic approximate vertex-labeled distance oracles for planar graphs, all with polylogarithmic query and update times, and nearly linear space requirement.
Dariusz Dereniowski and Dorota Urbańska-Osula: On-line Search in Two-Dimensional Environment
We consider the following on-line pursuit-evasion problem. A team of mobile agents called searchers starts at an arbitrary node of an unknown network. Their goal is to execute a search strategy that guarantees capturing a fast and invisible intruder regardless of its movements using as few searchers as possible. As a way of modeling two-dimensional shapes, we restrict our attention to networks that are embedded into partial grids: nodes are placed on the plane at integer coordinates and only nodes at distance one can be adjacent.
We give an on-line algorithm for the searchers that allow them to compute a connected and monotone strategy that guarantees searching any unknown partial grid with the use of $O(\sqrt{n})$ searchers, where $n$ is the number of nodes in the grid. We prove also a lower bound of $\Omega(\sqrt{n}/\log n)$ in terms of achievable competitive ratio of any on-line algorithm.
Vladimir Shenmaier: Complexity and Approximation of the Longest Vector Sum Problem
Given a set of n vectors in a d-dimensional normed space, consider the problem of finding a subset with the largest length of the sum vector. We prove that, for any ℓp norm, p∈[1,∞), the problem is hard to approximate within a factor better than min{α^{1/p},√α}, where α=16/17. In the general case, we show that the cardinality-constrained version of the problem is hard for approximation factors better than 1-1/ℯ and is W[2]-hard with respect to the cardinality of the solution. For both original and cardinality-constrained problems, we propose a randomized (1-ɛ)-approximation algorithm that runs in polynomial time when the dimension of space is O(log n). The algorithm has a linear time complexity for any fixed d and ɛ∈(0,1).
Felix Biermeier, Björn Feldkord, Manuel Malatyali and Friedhelm Meyer Auf der Heide: A communication-efficient dynamic distributed data structure for top-k and approximate-select queries
We consider the scenario of $n$ sensor nodes observing incoming streams of data. The nodes are connected to a central server whose task it is to compute some function over all data items observed by the nodes. In our case, there exists a total order on the data items observed by the nodes. Our goal is to compute the $k$ currently lowest observed values or a value with rank in $[(1-\varepsilon)k,(1+\varepsilon)k]$ with probability $(1-\delta)$. We propose solutions for these problems in an extension of the distributed monitoring model where the server can send broadcast messages to all nodes for unit cost. We want to minimize communication over multiple time steps where there are $m$ updates to a node’s value in between queries.
The result is composed of two main parts, which each may be of independent interest:
– Protocols which answer Top-$k$ and $k$-Select queries. These protocols are memoryless in the sense that they gather all information at the time of the request.
– A dynamic data structure which tracks for every $k$ an element close to $k$.
We describe how to combine the two parts to receive a protocol answering the stated queries over multiple time steps. Overall, we use $O(k + \log (m) + \log(\log(n)))$ messages in expectation for Top-$k$ queries and $O(\frac{1}{\varepsilon^2} \log (\frac{1}{\delta}) + \log(m) + \log^2(\log(n)))$ messages in expectation for $k$-Select queries. These results are shown to be asymptotically tight if $m$ is not too small.
Paz Carmi, Matthew Katz, Rachel Saban and Yael Stein: Improved PTASs for Convex Barrier Coverage
Let $R$ be a connected region in the plane and let $S$ be a set of $n$ points (representing mobile sensors) in the interior of $R$. We think of $R$’s boundary as a barrier which needs to be monitored. This gives rise to the barrier coverage problem, where one needs to move the sensors to the boundary of $R$, so that every point on the boundary is covered by one of the sensors. We focus on the variant of the problem where the goal is to place the sensors on $R$’s boundary, such that the distance (along $R$’s boundary) between any two adjacent sensors is equal to $R$’s perimeter over $n$ and the sum of the distances traveled by the sensors is minimum. In this paper, we consider the cases where $R$ is either a circle or a convex polygon. We present a PTAS for the circle case and explain how to overcome the main difficulties that arise when trying to adapt it to the convex polygon case. Our PTASs are significantly faster than the previous ones due to B. Bhattacharya, M. Burmester, Y. Hu, E. Kranakis, Q. Shi and A. Wiese. Moreover, our PTASs require efficient solutions to problems, which, as we observe, are equivalent to the circle-restricted and line-restricted Weber problems. Thus, we also devise efficient PTASs for these Weber problems.
Marcin Bienkowski, Artur Kraska and Paweł Schmidt: A Match in Time Saves Nine: Deterministic Online Matching With Delays
We consider the problem of online Min-cost Perfect Matching with Delays (MPMD) introduced by Emek et al. (STOC 2016). In this problem, an even number of requests appear in a metric space at different times and the goal of an online algorithm is to match them in pairs. In contrast to traditional online matching problems, in MPMD all requests appear online and an algorithm can match any pair of requests, but such decision may be delayed (e.g., to find a better match). The cost is the sum of matching distances and the introduced delays.
We present the first deterministic online algorithm for this problem. Its competitive ratio is O(m^(log 5.5)) = O(m^2.46), where 2 m is the number of requests. In particular, the bound does not depend on other parameters of the metric, such as its aspect ratio. Unlike previous (randomized) solutions for the MPMD problem, our algorithm does not need to know the metric space in advance and it does not require the space to be finite.
Martin Böhm, Łukasz Jeż, Jiří Sgall and Pavel Veselý: On Packet Scheduling with Adversarial Jamming and Speedup
In Packet Scheduling with Adversarial Jamming packets of arbitrary sizes arrive over time to be transmitted over a channel in which instantaneous jamming errors occur at times chosen by the adversary and not known to the algorithm. The transmission taking place at the time of jamming is corrupt, and the algorithm learns this fact immediately. An online algorithm maximizes the total size of packets it successfully transmits and the goal is to develop an algorithm with the lowest possible asymptotic competitive ratio, where the additive constant may depend on packet sizes.
Our main contribution is a universal algorithm that works for any speedup and packet sizes and, unlike previous algorithms for the problem, it does not need to know these properties in advance. We show that this algorithm guarantees 1-competitiveness with speedup 4, making it the first known algorithm to maintain 1-competitiveness with a moderate speedup in the general setting of arbitrary packet sizes. We also prove a lower bound of $\phi \approx 2.618$ on the speedup of any 1-competitive deterministic algorithm, showing that our algorithm is close to the optimum.
Additionally, we formulate a general framework for analyzing our algorithm locally and use it to show upper bounds on its competitive ratio for speedups in [1,4) and for several special cases, recovering some previously known results, each of which had a dedicated proof. In particular, our algorithm is 3-competitive without speedup, matching the algorithm and the lower bound of Jurdzinski et al. We use this framework also for the case of divisible packet sizes in which the size of a packet divides the size of any larger packet, to show that a slight modification of our algorithm is 1-competitive with speedup 2 and it achieves the optimal competitive ratio of 2 without speedup, again matching the algorithm and the lower bound of Jurdzinski et al.
Michele Flammini, Gianpiero Monaco and Qiang Zhang: Strategyproof Mechanisms for Additively Separable Hedonic Games and Fractional Hedonic Games
Additively separable hedonic games and fractional hedonic games have received considerable attention. They are coalition forming games of selfish agents based on their mutual preferences. Most of the work in the literature characterizes the existence and structure of stable outcomes (i.e., partitions in coalitions), assuming that preferences are given. However, there is little discussion on this assumption. In fact, agents receive different utilities if they belong to different partitions, and thus it is natural for them to declare their preferences strategically in order to maximize their benefit. In this paper we consider strategyproof mechanisms for additively separable hedonic games and fractional hedonic games, that is, partitioning methods without payments such that utility maximizing agents have no incentive to lie about their true preferences. We focus on social welfare maximization and provide several lower and upper bounds on the performance achievable by strategyproof mechanisms for general and specific additive functions. In most of the cases we provide tight or asymptotically tight results. All our mechanisms are simple and can be computed in polynomial time. Moreover, all the lower bounds are unconditional, that is, they do not rely on any computational or complexity assumptions.
Allan Borodin, Denis Pankratov and Amirali Salehi-Abari: On Conceptually Simple Algorithms for Variants of Online Bipartite Matching
We present a series of results regarding conceptually simple algorithms for bipartite matching in various online and related models. We first consider a deterministic adversarial model. The best approximation ratio possible for a one-pass deterministic online algorithm is $1/2$, which is achieved by any greedy algorithm. D\”urr \etal. \cite{Durr2016} recently presented a $2$-pass algorithm called \textsc{Category-Advice} that achieves approximation ratio $3/5$. We extend their algorithm to multiple passes. We prove the exact approximation ratio for the \textsc{$k$-pass Category-Advice} algorithm for all $k \ge 1$, and show that the approximation ratio converges to the inverse of the golden ratio $2/(1+\sqrt{5}) \approx 0.618$ as $k$ goes to infinity. The convergence is extremely fast — the \textsc{$5$-pass Category-Advice} algorithm is already within $0.01\%$ of the inverse of the golden ratio.
We then consider a natural greedy algorithm in the online stochastic IID model—\textsc{MinDegree}. This algorithm is an online version of a well-known and extensively studied offline algorithm \textsc{MinGreedy}. We show that \textsc{MinDegree} cannot achieve an approximation ratio better than $1-1/e$, which is guaranteed by any consistent greedy algorithm in the known IID model.
Finally, following the work in Besser and Poloczek \cite{BesserP17}, we depart from an adversarial or stochastic ordering and investigate a natural randomized algorithm (\textsc{MinRanking}) in the priority model. Although the priority model allows the algorithm to choose the input ordering in a general but well defined way, this natural algorithm cannot obtain the approximation of the \textsc{Ranking} algorithm in the ROM model.
Adrian Dumitrescu and Csaba Toth: Online Unit Clustering in Higher Dimensions
We revisit the online \textsc{Unit Clustering} problem in higher dimensions: Given a set of $n$ points in $\RR^d$, that arrive one by one, partition the points into clusters (subsets) of diameter at most one, so as to minimize the number of clusters used. In this paper, we work in $\RR^d$ using the $L_\infty$ norm. We show that the competitive ratio of any algorithm (deterministic or randomized) for this problem must depend on the dimension $d$. This resolves an open problem raised by Epstein and van Stee (WAOA 2008). We also give a randomized online algorithm with competitive ratio $O(d^2)$ for \textsc{Unit Clustering} of integer points (\ie, points in $\ZZ^d$, $d\in \NN$, under $L_{\infty}$ norm). We complement these results with some additional lower bounds for related problems in higher dimensions.
Naoyuki Kamiyama: Submodular Function Minimization with Submodular Set Covering Constraints and Precedence Constraints
In this paper, we consider the submodular function minimization problem with submodular set covering constraints and precedence constraints, and we prove that the algorithm of McCormick, Peis, Verschae, and Wierz for the precedence constrained covering problem can be generalized to our setting.
Jasper de Jong, Walter Kern, Berend Steenhuisen and Marc Uetz: The asymptotic price of anarchy for $k$-uniform congestion games
We consider the atomic version of congestion games with affine cost functions, and analyze the quality of worst case Nash equilibria when the strategy spaces of the players are restricted to be the bases of a $k$-uniform matroid. In this setting, for some parameter $k$, each player is to choose $k$ out of a finite set of resources, and the cost of a player for choosing a resource depends affine linearly on the number of players choosing the same resource.
Earlier work shows that the price of anarchy for this class of games is larger than $1.34$ but at most $2.15$. We determine a tight bound on the asymptotic price of anarchy equal to $\approx 1.35188$. Here, asymptotic refers to the fact that the bound holds for all instances with sufficiently many players. In particular, the asymptotic price of anarchy is bounded away from $4/3$. Our analysis also yields an upper bound on the price of anarchy $<1.4131$, for all instances.
Saeed Mehrabi: Approximating Domination on Intersection Graphs of Paths on a Grid
A graph G is called B_k-EPG (resp., B_k-VPG), for some constant k\geq 0, if it has a string representation on an axis-parallel grid such that each vertex is a path with at most k bends and two vertices are adjacent in G if and only if the corresponding strings share at least one grid edge (resp., the corresponding strings intersect each other). If two adjacent strings of a B_k-VPG graph intersect each other exactly once, then the graph is called a one-string B_k-VPG graph.
In this paper, we study the Minimum Dominating Set problem on B_1- EPG and B_1-VPG graphs. We first give an O(1)-approximation algorithm on one-string B_1-VPG graphs, providing the first constant-factor approximation algorithm for this problem. Moreover, we show that the Minimum Dominating Set problem is APX-hard on B_1-EPG graphs, ruling out the possibility of a PTAS unless P=NP. Finally, to complement our APX-hardness result, we give constant-factor approximation algorithms for the Minimum Dominating Set problem on two non-trivial subclasses of B_1-EPG graphs.
Alexander Mäcker, Manuel Malatyali, Friedhelm Meyer Auf der Heide and Sören Riechers: Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times
Consider a problem in which $n$ jobs that are classified into $k$ types arrive over time at their release times and are to be scheduled on a single machine so as to minimize the maximum flow time. The machine requires a setup taking $s$ time units whenever it switches from processing jobs of one type to jobs of a different type. We consider the problem as an online problem where each job is only known to the scheduler as soon as it arrives and where the processing time of a job only becomes known upon its completion (non-clairvoyance).
We are interested in the potential of simple greedy-like'' algorithms. We analyze a modification of the FIFO strategy and show its competitiveness to be $\Theta(\sqrt{n})$, which is optimal for the considered class of algorithms. For $k=2$ types it achieves a constant competitiveness. Our main insight is obtained by an analysis of the smoothed competitiveness. If processing times $p_j$ are independently perturbed by adding a value uniformly drawn from $[-\varepsilon p_j, \varepsilon p_j]$, $0 < \varepsilon < 1$, we obtain a competitiveness of $O(\varepsilon^{-2} \log^2 n)$. The result proves that bad instances are fragile andpractically” one might expect a much better performance than given by the $\Omega(\sqrt{n})$-bound.
Soroush Alamdari and David Shmoys: A bicriteria approximation algorithm for the k-center and k-median problems
The $k$-center and $k$-median problems are two central clustering techniques that are well-studied and widely used. In this paper, we focus on possible simultaneous generalizations of these two problems and present a bicriteria approximation algorithm for them with constant approximation factor in both dimensions. We also extend our results to the so-called incremental setting, where cluster centers are chosen one by one and the resulting solution must have the property that the first $k$ cluster centers selected must simultaneously be near-optimal for all values of $k$.
Abhijin Adiga, Alexander D. Friedman and Sharath Raghvendra: A k-median Based Online Algorithm for the stochastic k-server Problem
We consider the k-server problem in the random arrival model and present a simple k-median based algorithm for this problem. Let \sigma=\langle r_1,\ldots,r_n\rangle be the sequence of requests. Our algorithm will batch the requests into \log n groups where the (i+1)^{st} group contains requests \langle r_{2^i +1},\ldots, r_{2^{i+1}}\rangle. To process requests group $(i+1)$, our algorithm will place the $k$ servers at the $k$-median centers of the first $2^i$ requests. When a new request of this group arrives, the algorithm will simply assign the server associated with the nearest $k$-median center to serve it. We show that this simple algorithm, in the random arrival model, has a competitive ratio of at most $O(\alpha)$ and an additive error of $ O(\Delta k\log n)$, where $\Delta$ is the diameter of the requests and $\alpha$ is a lower bound on the competitive ratio of any online algorithm.
For our analysis, we note that in the random arrival model, the cost of serving the next request is minimized when servers are located at the $k$-median of the requests that have not yet arrived. But our algorithm instead uses the $k$-median of the requests seen so far as a proxy. If we use the existing analysis techniques, the bounds on the difference between $k$-median of the unprocessed requests and that of the processed requests is large. In particular, in addition to a constant factor of the optimal cost, for some $\epsilon > 0$, existing methods will also give an additive cost of $\epsilon n$ for serving $n$ requests. Our key contribution is in showing that when the number of processed and unprocessed requests are of comparable sizes, the cost of serving $n$ requests incurs only an additive cost of $k\Delta$ (significantly better than the previous methods). We apply this bound for serving each of the $\log n$ groups and obtain an overall bound which is $O(\alpha)$ times the optimal cost with an additive error of $O(k\Delta \log n)$.
Janusz Januszewski and Łukasz Zielonka: Online packing of rectangular items into square bins
Any list of rectangular items of total area not greater than 0.2837 can be packed online into the unit square. Furthermore, a 4.84-competitive 1-space bounded 2-dimensional bin packing algorithm is described and the lower bound of 3.246 is presented.