Approximation and Online Algorithms

In the Max k-Colored Clustering Problem we are given an undirected graph \(G = (V,E)\). Each edge \(e\) of \(G\) has a nonnegative weight \(w(e)\) and a color \(c(e)\in \mathcal{C}=\{1, 2,\ldots , k \}\). It is required to assign a color from \(\mathcal{C}\) to each vertex of \(G\) so as to maximize the total weight of edges whose both endpoints have the same color as the color of the edge. Angel et al. [1] show that the problem is strongly NP-hard and present a randomized constant-factor approximation algorithm for solving it. We improve this result in two directions. First, we give a more careful analysis of the algorithm in [1], which significantly improves on its approximation bound (\(0.25\) instead of \(1/e^2 \approx 0.135\)). Second, we present a different algorithm with a better worst case performance guarantee of \(7/23 \approx 0.304\). Both algorithms are based on using similar randomized rounding schemes for a natural LP relaxation of the problem. They can be derandomized in a standard way by computing conditional expectations for some estimate function.

Online matching on a line involves matching an online stream of items of various sizes to stored items of various sizes, with the objective of minimizing the average discrepancy in size between matched items. The best previously known upper and lower bounds on the optimal deterministic competitive ratio are linear in the number of items, and constant, respectively. We show that online matching on a line is essentially equivalent to a particular search problem, that we call \(k\) -lost cows. We then obtain the first deterministic sub-linearly competitive algorithm for online matching on a line by giving such an algorithm for the \(k\)-lost cows problem.

We give an algorithm for Online Bin Stretching with a stretching factor of \(1.5\) for any number of bins. We also show a specialized algorithm for three bins with a stretching factor of \(11/8 = 1.375\).

In the Colored Bin Packing problem a sequence of items of sizes up to \(1\) arrives to be packed into bins of unit capacity. Each item has one of \(c\ge 2\) colors and an additional constraint is that we cannot pack two items of the same color next to each other in the same bin. The objective is to minimize the number of bins.

In the important special case when all items have size zero, we characterize the optimal value to be equal to color discrepancy. As our main result, we give an (asymptotically) 1.5-competitive algorithm which is optimal. In fact, the algorithm always uses at most \(\lceil 1.5\cdot OPT \rceil \) bins and we show a matching lower bound of \(\lceil 1.5\cdot OPT \rceil \) for any value of \( OPT \ge 2\). For items of arbitrary size we give a lower bound of \(2.5\) and an absolutely \(3.5\)-competitive algorithm. We also show that classical algorithms First Fit, Best Fit and Worst Fit are not constant competitive.

In the case of two colors—the Black and White Bin Packing problem—we prove that all Any Fit algorithms have the absolute competitive ratio \(3\). When the items have sizes of at most \(1/d\) for a real \(d \ge 2\) we show that the Worst Fit algorithm is absolutely \((1+d/(d-1))\)-competitive.

We show a new algorithm and improved bound for the online square-into-square packing problem using a hybrid shelf-packing approach. This 2-dimensional packing problem involves packing an online sequence of squares into a unit square container without any two squares overlapping. We seek the largest area \(\alpha \) such that any set of squares with total area at most \(\alpha \) can be packed. We show an algorithm that packs any online sequence of squares with total area \(\alpha \le 2/5\), improving upon recent results of \(11/32\) [3] and \(3/8\) [8]. Our approach allows all squares smaller than a chosen maximum height \(h\) to be packed into the same fixed height shelf. We combine this with the introduction of variable height shelves for squares of height larger than \(h\). Some of these techniques can be extended to the more general problems of rectangle packing with rotation and bin packing.

We consider the Fault-Tolerant Facility Placement problem (\(FTFP\)), which is a generalization of the classical Uncapacitated Facility Location problem (\(UFL\)). In the \(FTFP\) problem we have a set of clients \(C\) and a set of facilities \(F\). Each facility \(i \in F\) can be opened many times. For each opening of facility \(i\) we pay \(f_i \ge 0\). Our goal is to connect each client \(j \in C\) with \(r_j \ge 1\) open facilities in a way that minimizes the total cost of open facilities and established connections.

In a series of recent papers \(FTFP\) was essentially reduced to Fault-Tolerant Facility Location problem (\(FTFL\)) and then to \(UFL\) showing it could be approximated with ratio \(1.575\). In this paper we show that \(FTFP\) can actually be approximated even better. We consider approximation ratio as a function of \(r = min_{j \in C}~r_j\) (minimum requirement of a client). With increasing \(r\) the approximation ratio of our algorithm \(\lambda _r\) converges to one. Furthermore, for \(r > 1\) the value of \(\lambda _r\) is less than 1.463 (hardness of approximation of \(UFL\)). We also show a lower bound of 1.278 for the approximability of the \(FTFL\) for arbitrary \(r\). Already for \(r > 3\) we obtain that \(FTFP\) can be approximated with ratio 1.275, showing that under standard complexity theoretic assumptions \(FTFP\) is strictly better approximable than \(FTFL\).

In this paper we consider natural generalizations of the facility location problem and the joint replenishment problem in which the opening cost of facilities and the ordering cost over the planning horizon is characterized by a submodular set function in the oracle model. Specifically, we can access the function only through a blackbox that returns the value of the function for a given set. We prove information theoretic lower bounds that these two problems cannot be approximated by any polynomial-time algorithm better than a ratio of \(O(\sqrt{n}/\log ^2{n})\). Moreover, we give \(O(\sqrt{n}\cdot \log n)\)-approximation algorithms for the two problems.

We consider the problem of online graph multi-coloring with advice. Multi-coloring is often used to model frequency allocation in cellular networks. We give several nearly tight upper and lower bounds for the most standard topologies of cellular networks, paths and hexagonal graphs. For the path, negative results trivially carry over to bipartite graphs, and our positive results are also valid for bipartite graphs. The advice given represents information that is likely to be available, studying for instance the data from earlier similar periods of time.

Let \(R\) be a finite set of terminals in a metric space \((M,d)\). We consider finding a minimum size set \(S \subseteq M\) of additional points such that the unit-disc graph \(G[R \cup S]\) of \(R \cup S\) satisfies some connectivity properties. In the Steiner Tree with Minimum Number of Steiner Points (ST-MSP) problem \(G[R \cup S]\) should be connected. In the more general Steiner Forest with Minimum Number of Steiner Points (SF-MSP) problem we are given a set \(D \subseteq R \times R\) of demand pairs and \(G[R \cup S]\) should contains a \(uv\)-path for every \(uv \in D\). Let \(\varDelta \) be the maximum number of points in a unit ball such that the distance between any two of them is larger than \(1\). It is known that \(\varDelta =5\) in \(\mathbb {R}^2\). The previous known approximation ratio for ST-MSP was \(\lfloor (\varDelta +1)/2 \rfloor +1+\epsilon \) in an arbitrary normed space [15], and \(2.5+\epsilon \) in the Euclidean space \(\mathbb {R}^2\) [5]. Our approximation ratio for ST-MSP is \(1+\ln (\varDelta -1)+\epsilon \) in an arbitrary normed space, which in \(\mathbb {R}^2\) reduces to \(1+\ln 4+\epsilon < 2.3863 +\epsilon \). For SF-MSP we give a simple \(\varDelta \)-approximation algorithm, improving the folklore ratio \(2(\varDelta -1)\). Finally, we generalize and simplify the \(\varDelta \)-approximation of Calinescu [3] for the \(2\) -Connectivity-MSP problem, where \(G[R \cup S]\) should be \(2\)-connected.

We improve complexity bounds for energy-efficient non-preemptive scheduling problems for both the single processor and multi-processor cases. As energy conservation has become a major concern, traditional scheduling problems have been revisited in the past few years to take into account the energy consumption [1]. We consider the speed scaling setting introduced by Yao et al. [20] where a set of jobs, each with a release date, deadline and work volume, are to be scheduled on a set of identical processors. The processors may change speed as a function of time and the energy they consume is the \(\alpha \)th power of their speed integrated over time. The objective is then to find a feasible non-preemptive schedule which minimizes the total energy used.

We show that for an arbitrarily number of processors and jobs with equal work volumes there is a \(2(1+\varepsilon )(5(1+\varepsilon ))^{\alpha -1}\tilde{B}_{\alpha }=O_{\alpha }(1)\) approximation algorithm, where \(\tilde{B}_{\alpha }\) is the generalized Bell number. This is the first constant factor algorithm for the multi-processor case, and this also extends to arbitrary processor-dependent work volumes, up to losing a factor of \((\frac{(1+r)r}{2})^{\alpha }\) in the approximation, where \(r\) is the maximum ratio between two work volumes. For the single processor case, we introduce a new linear programming formulation of speed scaling, using a new constraint capturing non-preemption, and prove that its integrality gap is at most \(12^{\alpha -1}\). With our new constraint we improve on the previously known unbounded integrality gap of at least \(\varOmega (n^{\alpha -1})\). Finally, we deal with the inapproximabilty of speed scaling and we prove that the multi-processor case is APX-hard, even in the special case where all release dates and deadlines are equal and \(r\) is 4.

Cooperation between mobile robots and wireless sensor networks is a line of research that is currently attracting a lot of attention. In this context, we study the following problem of barrier coverage by stationary wireless sensors that are assisted by a mobile robot with the capacity to move sensors. Assume that \(n\) sensors are initially arbitrarily distributed on a line segment barrier. Each sensor is said to cover the portion of the barrier that intersects with its sensing area. Owing to incorrect initial position, or the death of some of the sensors, the barrier is not completely covered by the sensors. We employ a mobile robot to move the sensors to final positions on the barrier such that barrier coverage is guaranteed. We seek algorithms that minimize the length of the robot’s trajectory, since this allows the restoration of barrier coverage as soon as possible. We give an optimal linear-time offline algorithm that gives a minimum-length trajectory for a robot that starts at one end of the barrier and achieves the restoration of barrier coverage. We also study two different online models: one in which the online robot does not know the length of the barrier in advance, and the other in which the online robot knows it in advance. For the case when the online robot does not know the length of the barrier, we prove a tight bound of \(3/2\) on the competitive ratio, and we give a tight lower bound of \(5/4\) on the competitive ratio in the other case. Thus for each case we give an optimal online algorithm.

Numerous approximation algorithms for unit disk graphs have been proposed in the literature, exhibiting sharp trade-offs between running times and approximation ratios. We propose a method to obtain linear-time approximation algorithms for unit disk graph problems. Our method yields linear-time \((4\,+\,\varepsilon )\)-approximations to the maximum-weight independent set and the minimum dominating set, bringing dramatic performance improvements when compared to previous algorithms that achieve the same approximation factors. Furthermore, we present an alternative linear-time approximation scheme for the minimum vertex cover, which could be obtained by an indirect application of our method.

We consider the Minimum Feasible Tileset problem: Given a set of symbols and subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols (tiles) such that each scenario can be formed by selecting at most one symbol from each tile. We show that this problem is \(\mathsf {NP}\)-complete even if each scenario contains at most three symbols. Our main result is a 4/3-approximation algorithm for the general case. In addition, we show that the Minimum Feasible Tileset problem is fixed-parameter tractable both when parameterized with the number of scenarios and with the number of symbols.

Ad exchanges are becoming an increasingly popular way to sell advertisement slots on the internet. An ad exchange is basically a spot market for ad impressions. A publisher who has already signed contracts reserving advertisement impressions on his pages can choose between assigning a new ad impression for a new page view to a contracted advertiser or to sell it at an ad exchange. This leads to an online revenue maximization problem for the publisher. Given a new impression to sell decide whether (a) to assign it to a contracted advertiser and if so to which one or (b) to sell it at the ad exchange and if so at which reserve price. We make no assumptions about the distribution of the advertiser valuations that participate in the ad exchange and show that there exists a simple primal-dual based online algorithm, whose lower bound for the revenue converges to \(R_{ADX} + R_A (1 - 1/e)\), where \(R_{ADX}\) is the revenue that the optimum algorithm achieves from the ad exchange and \(R_A\) is the revenue that the optimum algorithm achieves from the contracted advertisers.

We present a factor \(14D^2\) approximation algorithm for the minimum linear arrangement problem on series-parallel graphs, where \(D\) is the maximum degree in the graph. Given a suitable decomposition of the graph, our algorithm runs in time \(O(|E|)\) and is very easy to implement. Its divide-and-conquer approach allows for an effective parallelization. Note that a suitable decomposition can also be computed in time \(O(|E|\log {|E|})\) (or even \(O(\log {|E|}\log ^*{|E|})\) on an EREW PRAM using \(O(|E|)\) processors).

For the proof of the approximation ratio, we use a sophisticated charging method that uses techniques similar to amortized analysis in advanced data structures.

On general graphs, the minimum linear arrangement problem is known to be NP-hard. To the best of our knowledge, the minimum linear arrangement problem on series-parallel graphs has not been studied before.

We study a dual version of online edge coloring, where the goal is to color as many edges as possible using only a given number, \(k\), of available colors. All of our results are with regard to competitive analysis. For paths, we consider \(k=2\), and for trees, we consider any \(k \ge 2\). We prove that a natural greedy algorithm called First-Fit is optimal among deterministic algorithms on paths as well as trees. This is the first time that an optimal algorithm for online dual edge coloring has been identified for a class of graphs. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. Again, it is the first time that this has been done for a class of graphs. For trees, we also show that even randomized algorithms cannot be much better than First-Fit.

We consider the problem of scheduling packets of different lengths via a directed communication link prone to jamming errors. Dynamic packet arrivals and errors are modelled by an adversary. We focus on estimating competitive throughput of online scheduling algorithms. We design an online algorithm for scheduling packets of arbitrary lengths, achieving optimal competitive throughput in \((1/3,1/2]\) (the exact value depends on packet lengths). Another algorithm we design makes use of additional resources in order to achieve competitive throughput \(1\), that is, it achieves at least as high throughput as the best schedule without such resources, for any arrival and jamming patterns. More precisely, we show that if the algorithm can run with double speed, i.e., with twice higher frequency, then its competitive throughput is \(1\). This demonstrates that throughput of the best online fault-tolerant scheduling algorithms scales well with resource augmentation. Finally, we generalize the first of our algorithms to the case of any \(f\ge 1\) channels and obtain competitive throughput \(1/2\) in this setting in case packets lengths are pairwise divisible (i.e., any larger is divisible by any smaller).

In \(k\)-hypergraph matching, we are given a collection of sets of size at most \(k\), each with an associated weight, and we seek a maximum-weight subcollection whose sets are pairwise disjoint. More generally, in \(k\)-hypergraph \(b\)-matching, instead of disjointness we require that every element appears in at most \(b\) sets of the subcollection. Our main result is a linear-programming based \((k-1+\tfrac{1}{k})\)-approximation algorithm for \(k\)-hypergraph \(b\)-matching. This settles the integrality gap when \(k\) is one more than a prime power, since it matches a previously-known lower bound. When the hypergraph is bipartite, we are able to improve the approximation ratio to \(k-1\), which is also best possible relative to the natural LP. These results are obtained using a more careful application of the iterated packing method.

Using the bipartite algorithmic integrality gap upper bound, we show that for the family of combinatorial auctions in which anyone can win at most \(t\) items, there is a truthful-in-expectation polynomial-time auction that \(t\)-approximately maximizes social welfare. We also show that our results directly imply new approximations for a generalization of the recently introduced bounded-color matching problem.We also consider the generalization of \(b\)-matching to demand matching, where edges have nonuniform demand values. The best known approximation algorithm for this problem has ratio \(2k\) on \(k\)-hypergraphs. We give a new algorithm, based on local ratio, that obtains the same approximation ratio in a much simpler way.

We consider the Minimum Elmore Delay Steiner Tree Problem, which arises as a key problem in the routing step in VLSI design: Here, we are given a set of pins located on the chip which have to be connected by metal wires in order to make the propagation of electrical signals possible. Challenging timing constraints require that these electrical signals travel as fast as possible. This is modeled as a problem of constructing a Steiner tree minimizing the Elmore delay [9] between a source vertex and a set of sink vertices. The problem is strongly \(NP\)-hard even for very restricted special cases, and although it is central in VLSI design (see e.g. [18]), no approximation algorithms were known until today.

In this work, we give the first constant-factor approximation algorithm. The algorithm achieves an approximation ratio of \(3.39\) in the rectilinear plane and \(4.11\) in metric graphs. We also demonstrate that our algorithm brings improvements on real world VLSI instances compared to the currently used standard method of computing short Steiner trees.

We study online preemptive makespan minimization on \(m\) parallel machines, where the (multiprocessor) jobs arrive over time and have widths from some fixed set \(W\subseteq \{1,2,\ldots ,m\}\). For every number \(m\) of machines we concisely characterize all the sets \(W\) for which there is a \(1\)-competitive fully online algorithm and all the sets \(W\) for which there is a \(1\)-competitive nearly online algorithm.

The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem (TSP), the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we give the first constant-factor approximation for a priori TRP.

A covering problem is an integer linear program of type \(\min \{c^Tx\mid Ax\ge D,\ 0\le x\le d,\ x \text{ integral }\}\) where \(A\in \mathbb {Z}^{m\times n}_+\), \(D\in \mathbb {Z}_+^m\), and \(c,d\in \mathbb {Z}_+^n\). In this paper, we study covering problems with additional precedence constraints \(\{x_i\le x_j \ \forall j\preceq i \in \mathcal {P}\}\), where \(\mathcal {P}=([n], \preceq )\) is some arbitrary, but fixed partial order on the items represented by the column-indices of \(A\). Such precedence constrained covering problems (PCCP) are of high theoretical and practical importance even in the special case of the precedence constrained knapsack problem, i.e., where \(m=1\) and \(d\equiv 1\).

Our main result is a strongly-polynomial primal-dual approximation algorithm for PCCP with \(d\equiv 1\). Our approach generalizes the well-known knapsack cover inequalities to obtain an IP formulation which renders any explicit precedence constraints redundant. The approximation ratio of this algorithm is upper bounded by the width of \(\mathcal {P}\), i.e., by the size of a maximum antichain in \(\mathcal {P}\). Interestingly, this bound is independent of the number of constraints. We are not aware of any other results on approximation algorithms for PCCP on arbitrary posets \(\mathcal {P}\). For the general case with , we present pseudo-polynomial algorithms.