Approximation and Online Algorithms

A graph \(G = (V,E)\) is terrain-like if one can assign a unique integer from the range [1..|V|] to each vertex in V, such that, if both \(\{i,k\}\) and \(\{j,l\}\) are in E, for any \(i< j< k < l\), then so is \(\{i,l\}\). We present a local-search-based PTAS for minimum dominating set in terrain-like graphs. Then, we observe that, besides the visibility graphs of x-monotone terrains which are terrain-like, so are the visibility graphs of weakly-visible polygons and weakly-visible terrains, immediately implying a PTAS for guarding the vertices of such a polygon or terrain from its vertices. We also present PTASs for continuously guarding the boundary of a WV-polygon or WV-terrain, either from its vertices, or, for a WV-terrain, from arbitrary points on the terrain. Finally, we compare between terrain-like graphs and non-jumping graphs, and also observe that both families admit PTASs for maximum independent set.

We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278.

We demonstrate for the first time the advantage of branching and the applicability of full adaptivity in the design of lower bounds for the classic online bin packing problem. We apply a new method for weight based analysis, which is usually applied only in proofs of upper bounds. The values of previous lower bounds were approximately 1.5401 and 1.5403.

The k-Canadian Traveller Problem consists in finding the optimal way from a source s to a target t on an undirected weighted graph G, knowing that at most k edges are blocked. The traveller, guided by a strategy, sees an edge is blocked when he visits one of its endpoints. A major result established by Westphal is that the competitive ratio of any deterministic strategy for this problem is at least \(2k+1\). reposition and comparison strategies achieve this bound.

We refine this analysis by focusing on graphs with a maximum (s, t)-cut size \(\mu _{\text {max}}\) less than k. A strategy called detour is proposed and its competitive ratio is \(2\mu _{\text {max}}+ \sqrt{2}(k-\mu _{\text {max}}) + 1\) when \(\mu _{\text {max}}< k\) which is strictly less than \(2k+1\). Moreover, when \(\mu _{\text {max}}\ge k\), the competitive ratio of detour is \(2k+1\) and is optimal. Therefore, detour improves the competitiveness of the deterministic strategies known up to now.

Online algorithms that allow a small amount of migration or recourse have been intensively studied in the last years. They are essential in the design of competitive algorithms for dynamic problems, where objects can also depart from the instance. In this work, we give a general framework to obtain so called robust online algorithms for a variety of dynamic problems: these online algorithms achieve an asymptotic competitive ratio of \(\gamma +\epsilon \) with migration \(O(1/\epsilon )\), where \(\gamma \) is the best known offline asymptotic approximation ratio. For our framework, we require only two ingredients: (i) the existence of an online algorithm for the static case (without departures) that provides a provably good solution compared to the total volume of the instance and (ii) that the optimal solution always exceeds this total volume. If these criteria are met, we can complement the online algorithm with any offline algorithm.

We study approximation algorithms for the problem of minimizing the makespan on a set of machines with uncertainty on the processing times of jobs. In the model we consider, which goes back to [3], once the schedule is defined an adversary can pick a scenario where deviation is added to some of the jobs’ processing times. Given only the maximal cardinality of these jobs, and the magnitude of potential deviation for each job, the goal is to optimize the worst-case scenario. We consider both the cases of identical and unrelated machines. Our main result is an EPTAS for the case of identical machines. We also provide a 3-approximation algorithm and an inapproximability ratio of \(2-\epsilon \) for the case of unrelated machines.

Problems involving the efficient arrangement of simple objects, as captured by bin packing and makespan scheduling, are fundamental tasks in combinatorial optimization. These are well understood in the traditional online and offline cases, but have been less well-studied when the volume of the input is truly massive, and cannot even be read into memory. This is captured by the streaming model of computation, where the aim is to approximate the cost of the solution in one pass over the data, using small space. As a result, streaming algorithms produce concise input summaries that approximately preserve the optimum value.

We design the first efficient streaming algorithms for these fundamental problems in combinatorial optimization. For Bin Packing, we provide a streaming asymptotic \(1+\varepsilon \)-approximation with \(\widetilde{\mathcal {O}}\left( \frac{1}{\varepsilon }\right) \) memory, where \(\widetilde{\mathcal {O}}\) hides logarithmic factors. Moreover, such a space bound is essentially optimal. Our algorithm implies a streaming \(d+\varepsilon \)-approximation for Vector Bin Packing in d dimensions, running in space \(\widetilde{\mathcal {O}}\left( \frac{d}{\varepsilon }\right) \). For the related Vector Scheduling problem, we show how to construct an input summary in space \(\widetilde{\mathcal {O}}(d^2\cdot m / \varepsilon ^2)\) that preserves the optimum value up to a factor of \(2 - \frac{1}{m} +\varepsilon \), where m is the number of identical machines.

The Ring Loading Problem emerged in the 1990s to model an important special case of telecommunication networks (SONET rings) which gained attention from practitioners and theorists alike. Given an undirected cycle on n nodes together with non-negative demands between any pair of nodes, the Ring Loading Problem asks for an unsplittable routing of the demands such that the maximum cumulated demand on any edge is minimized. Let L be the value of such a solution. In the relaxed version of the problem, each demand can be split into two parts where the first part is routed clockwise while the second part is routed counter-clockwise. Denote with \(L^*\) the maximum load of a minimum split routing solution. In a landmark paper, Schrijver, Seymour and Winkler [22] showed that \(L \le L^* + \frac{3}{2}D\), where D is the maximum demand value. They also found (implicitly) an instance of the Ring Loading Problem with \(L = L^* + \frac{101}{100}D\). Recently, Skutella [25] improved these bounds by showing that \(L \le L^* + \frac{19}{14}D\), and there exists an instance with \(L = L^* + \frac{11}{10}D\). We contribute to this line of research by showing that \(L \le L^* + \frac{13}{10}D\). We also take a first step towards lower and upper bounds for small instances.

We study parallel online algorithms: For some fixed integer k, a collective of k parallel processes that perform online decisions on the same sequence of events forms a k-copy algorithm. For any given time and input sequence, the overall performance is determined by the best of the k individual total results. Problems of this type have been considered for online makespan minimization; they are also related to optimization with advice on future events, i.e., a number of bits available in advance.

We develop Predictive Harmonic\(_3\) (PH3), a relatively simple family of k-copy algorithms for the online Bin Packing Problem, whose joint competitive factor converges to 1.5 for increasing k. In particular, we show that \(k=6\) suffices to guarantee a factor of 1.5714 for PH3, which is better than 1.57829, the performance of the best known 1-copy algorithm Advanced Harmonic, while \(k=11\) suffices to achieve a factor of 1.5406, beating the known lower bound of 1.54278 for a single online algorithm. In the context of online optimization with advice, our approach implies that 4 bits suffice to achieve a factor better than this bound of 1.54278, which is considerably less than the previous bound of 15 bits.

We extend the Mobile Server Problem introduced in [8] to a model where k identical mobile resources, here named servers, answer requests appearing at points in the Euclidean space. In order to reduce communication costs, the positions of the servers can be adapted by a limited distance \(m_s\) per round for each server. The costs are measured similar to the classical Page Migration Problem, i.e., answering a request induces costs proportional to the distance to the nearest server, and moving a server induces costs proportional to the distance multiplied with a weight D.

We show that, in our model, no online algorithm can have a constant competitive ratio, i.e., one which is independent of the input length n, even if an augmented moving distance of \((1+\delta )m_s\) is allowed for the online algorithm. Therefore we investigate a restriction of the power of the adversary dictating the sequence of requests: We demand locality of requests, i.e., that consecutive requests come from points in the Euclidean space with distance bounded by some constant \(m_c\). We show constant lower bounds on the competitiveness in this setting (independent of n, but dependent on k, \(m_s\) and \(m_c\)).

On the positive side, we present a deterministic online algorithm with bounded competitiveness when augmented moving distance and locality of requests is assumed. Our algorithm simulates any given algorithm for the classical k-Page Migration problem as guidance for its servers and extends it by a greedy move of one server in every round. The resulting competitive ratio is polynomial in the number of servers k, the ratio between \(m_c\) and \(m_s\), the inverse of the augmentation factor \(\nicefrac {1}{\delta }\) and the competitive ratio of the simulated k-Page Migration algorithm.

In the k-Connectivity Augmentation Problem we are given a k-edge-connected graph and a set of additional edges called links. Our goal is to find a set of links of minimum cardinality whose addition to the graph makes it \((k+1)\)-edge-connected. There is an approximation preserving reduction from the mentioned problem to the case \(k=1\) (a.k.a. the Tree Augmentation Problem or TAP) or \(k=2\) (a.k.a. the Cactus Augmentation Problem or CacAP). While several better-than-2 approximation algorithms are known for TAP, nothing better is known for CacAP (hence for k-Connectivity Augmentation in general).

As a first step towards better approximation algorithms for CacAP, we consider the special case where the input cactus consists of a single cycle, the Cycle Augmentation Problem (CycAP). This apparently simple special case retains part of the hardness of the general case. In particular, we are able to show that it is \(\mathrm {APX}\)-hard.

In this paper we present a combinatorial \(\left( \frac{3}{2}+\varepsilon \right) \)-approximation for CycAP, for any constant \(\varepsilon >0\). We also present an LP formulation with a matching integrality gap: this might be useful to address the general case of the problem.

We show that the strong chromatic index of unit disk graphs is efficiently 6-approximable. This improves on 8-approximability as shown by Barrett, Istrate, Kumar, Marathe, Thite, and Thulasidasan [1]. We also show that strong edge-6-colourability is NP-complete for the class of unit disk graphs. Thus there is no polynomial-time \((7/6-\varepsilon )\)-approximation unless P = NP.

We consider a single-machine scheduling problem with bipartite AND/OR-constraints that is a natural generalization of (precedence-constrained) min-sum set cover. For min-sum set cover, Feige, Lovàsz and Tetali [15] showed that the greedy algorithm has an approximation guarantee of 4, and obtaining a better approximation ratio is NP-hard. For precedence-constrained min-sum set cover, McClintock, Mestre and Wirth [30] proposed an \(O(\sqrt{m})\)-approximation algorithm, where m is the number of sets. They also showed that obtaining an algorithm with performance \(O(m^{1/12-\varepsilon })\) is impossible, assuming the hardness of the planted dense subgraph problem.

The more general problem examined here is itself a special case of scheduling AND/OR-networks on a single machine, which was studied by Erlebach, Kääb and Möhring [13]. Erlebach et al. proposed an approximation algorithm whose performance guarantee grows linearly with the number of jobs, which is close to best possible, unless P = NP.

For the problem considered here, we give a new LP-based approximation algorithm. Its performance ratio depends only on the maximum number of OR-predecessors of any one job. In particular, in many relevant instances, it has a better worst-case guarantee than the algorithm by McClintock et al., and it also improves upon the algorithm by Erlebach et al. (for the special case considered here).

Yet another important generalization of min-sum set cover is generalized min-sum set cover, for which a 12.4-approximation was derived by Im, Sviridenko and Zwaan [23]. Im et al. conjecture that generalized min-sum set cover admits a 4-approximation, as does min-sum set cover. In support of this conjecture, we present a 4-approximation algorithm for another interesting special case, namely when each job requires that no less than all but one of its predecessors are completed before it can be processed.

In a clustering with outliers problem, we are required to cluster all but a specified number of points, called outliers. In a fault tolerant clustering problem, the objective function incorporates the distance of a point to its f-th closest center chosen in the solution. We combine these two orthogonal generalizations, and consider Fault Tolerant Clustering with Outliers problems for various clustering objectives, such as k-center, k-median, and sum of radii. We essentially reduce the Fault Tolerant Clustering with Outliers problem, to the corresponding (non Fault Tolerant) Clustering with Outliers problem, for which constant approximations are known. This can be seen as a generalization of the framework of Kumar and Raichel [20] to handle the presence of outliers. This reduction comes at a loss in the approximation guarantee; however, we show that it is bounded by O(1) for the k-center objective, whereas it is O(f) for k-median and sum of radii objectives, where f is the degree of Fault Tolerance required in the solution. This implies O(1) and O(f) approximations for these generalizations respectively.

In the \(d\)-Scattered Set problem we are asked to select at least k vertices of a given graph, so that the distance between any pair is at least d. We study the problem’s (in-)approximability and offer improvements and extensions of known results for Independent Set, of which the problem is a generalization. Specifically, we show:

We study online scheduling of unit-sized jobs in two related problems, namely, restricted assignment problem and smart grid problem. The input to the two problems are in close analogy but the objective functions are different. We show that the greedy algorithm is an optimal online algorithm for both problems. Typically, an online algorithm is proved to be an optimal online algorithm through bounding its competitive ratio and showing a lower bound with matching competitive ratio. However, our analysis does not take this approach. Instead, we prove the optimality without giving the exact bounds on competitive ratio. Roughly speaking, given any online algorithm and a job instance, we show the existence of another job instance for greedy such that (i) the two instances admit the same optimal offline schedule; (ii) the cost of the online algorithm is at least that of the greedy algorithm on the respective job instance. With these properties, we can show that the competitive ratio of the greedy algorithm is the smallest possible.

We study fair clustering problems as proposed by Chierichetti et al. [CKLV17]. Here, points have a sensitive attribute and all clusters in the solution are required to be balanced with respect to it (to counteract any form of data-inherent bias). Previous algorithms for fair clustering do not scale well. We show how to model and compute so-called coresets for fair clustering problems, which can be used to significantly reduce the input data size. We prove that the coresets are composable [IMMM14] and show how to compute them in a streaming setting. This yields a streaming PTAS for fair k-means in the case of two colors (and exact balances). Furthermore, we extend techniques due to Chierichetti et al. [CKLV17] to obtain an approximation algorithm for k-means, which leads to a constant factor algorithm in the streaming model when combined with the coreset.