Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

We present polylogarithmic approximations for the R|prec|C _max and R|prec|∑ _j w _j C _j problems, when the precedence constraints are “treelike”—i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated machines with precedence constraints of any kind. We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment—this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion + dilation”, as in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617–632, 1994). The first step in our algorithm for the R|prec|C _max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function. A preliminary version of this paper appeared in the Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 146–157, 2005. V.S. Anil Kumar supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. M.V. Marathe supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. Part of this work by S. Parthasarathy was done while at the Department of Computer Science, University of Maryland, College Park, MD 20742, and in part while visiting the Los Alamos National Laboratory. Research supported in part by NSF Award CCR-0208005 and NSF ITR Award CNS-0426683. Research of A. Srinivasan supported in part by NSF Award CCR-0208005, NSF ITR Award CNS-0426683, and NSF Award CNS-0626636.     

Network Design with Weighted Players

We consider a model of game-theoretic network design initially studied by Anshelevich et al. (Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pp. 295–304, 2004), where selfish players select paths in a network to minimize their cost, which is prescribed by Shapley cost shares. If all players are identical, the cost share incurred by a player for an edge in its path is the fixed cost of the edge divided by the number of players using it. In this special case, Anshelevich et al. (Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pp. 295–304, 2004) proved that pure-strategy Nash equilibria always exist and that the price of stability—the ratio between the cost of the best Nash equilibrium and that of an optimal solution—is Θ(log k), where k is the number of players. Little was known about the existence of equilibria or the price of stability in the general weighted version of the game. Here, each player i has a weight w _i ≥1, and its cost share of an edge in its path equals w _i times the edge cost, divided by the total weight of the players using the edge. This paper presents the first general results on weighted Shapley network design games. First, we give a simple example with no pure-strategy Nash equilibrium. This motivates considering the price of stability with respect to α-approximate Nash equilibria—outcomes from which no player can decrease its cost by more than an α multiplicative factor. Our first positive result is that O(log w _max)-approximate Nash equilibria exist in all weighted Shapley network design games, where w _max is the maximum player weight. More generally, we establish the following trade-off between the two objectives of good stability and low cost: for every α=Ω(log w _max), the price of stability with respect to O(α)-approximate Nash equilibria is O((log W)/α), where W is the sum of the players’ weights. In particular, there is always an O(log W)-approximate Nash equilibrium with cost within a constant factor of optimal. Finally, we show that this trade-off curve is nearly optimal: we construct a family of networks without o(log w _max/ log log w _max)-approximate Nash equilibria, and show that for all α=Ω(log w _max/log log w _max), achieving a price of stability of O(log W/α) requires relaxing equilibrium constraints by an Ω(α) factor. Research of H.-L. Chen supported in part by NSF Award 0323766. Research of T. Roughgarden supported in part by ONR grant N00014-04-1-0725, DARPA grant W911NF-04-9-0001, and an NSF CAREER Award.     

Generalization of EDF and LLF: Identifying All Optimal Online Algorithms for Minimizing Maximum Lateness

It is well known that the Earliest-Deadline-First (EDF) and the Least-Laxity-First (LLF) algorithms are optimal algorithms for the problem of preemptively scheduling jobs that arrive over time on a single machine to minimize the maximum lateness (1|r _j ,pmtn|L _max). It was not previously known what other online algorithms are optimal for this problem. As this problem is fundamental in machine scheduling, it deserves a thorough investigation. In this paper, the concept of compound laxity is introduced, and a complete characterization of all optimal online algorithms for this problem is derived.     

Algorithms for some maximization scheduling problems on a single machine

In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness 1‖max-ΣT _j and for the problem of maximizing the number of tardy jobs 1‖maxΣU _j . In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem 1‖max-ΣT _j is polynomially solvable. For several special cases of problem 1‖maxΣT _j , we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.     

Scheduling algorithms for procrastinators

This paper presents scheduling algorithms for procrastinators, where the speed that a procrastinator executes a job increases as the due date approaches. We give optimal off-line scheduling policies for linearly increasing speed functions. We then explain the computational/numerical issues involved in implementing this policy. We next explore the online setting, showing that there exist adversaries that force any online scheduling policy to miss due dates. This impossibility result motivates the problem of minimizing the maximum interval stretch of any job; the interval stretch of a job is the job’s flow time divided by the job’s due date minus release time. We show that several common scheduling strategies, including the “hit-the-highest-nail” strategy beloved by procrastinators, have arbitrarily large maximum interval stretch. Then we give the “thrashing” scheduling policy and show that it is a Θ(1) approximation algorithm for the maximum interval stretch. Research of M.A. Bender was supported in part by NSF Grants CCR-0208670, CCF-0621439/0621425, CCF-0540897/05414009, CCF-0634793/0632838, and CNS-0627645.     

Cost-Sharing Mechanisms for Network Design

We consider a single-source network design problem from a game-theoretic perspective. Gupta, Kumar and Roughgarden (Proc. 35th Annual ACM STOC, pp. 365–372, 2003) developed a simple method for a single-source rent-or-buy problem that also yields the best-known approximation ratio for the problem. We show how to use a variant of this method to develop an approximately budget-balanced and group strategyproof cost-sharing method for the problem. The novelty of our approach stems from our obtaining the cost-sharing methods for the rent-or-buy problem by carefully combining cost-shares for the simpler Steiner tree problem. Our algorithm is conceptually simpler than the previous such cost-sharing method due to Pál and Tardos (Proc. 44th Annual FOCS, pp. 584–593, 2003), and improves the previously-known approximation factor of 15 to 4.6. A preliminary version of this work appears in the Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2004. This research was done in part during the IMA Workshop on Network Management and Design at the University of Minnesota, April 2003. A. Gupta supported in part by an NSF CAREER award CCF-0448095, and by an Alfred P. Sloan Fellowship. A. Srinivasan supported in part by the National Science Foundation under Grant No. 0208005 and ITR Award CNS-0426683. Research of é. Tardos supported in part by ONR grant N00014-98-1-0589, and NSF grants CCR-0311333 and CCR-0325453.     

A randomized clustering of anonymous wireless ad hoc networks with an application to the initialization problem

The Distributed Mobility-Adaptive Clustering (DMAC) due to Basagni partitions the nodes of a mobile ad hoc network into clusters, thus giving the network a hierarchical organization. This algorithm supports the mobility of the nodes, even during the cluster formation. The main feature of DMAC is that in a weighted network (in which two or more nodes cannot have the same weight), nodes have to choose the clusterheads taking into account only the node weight, i.e. the mobility when a node weight is the inverse of its speed. In our approach many nodes may have the same speed and hence the same weight. We assume that nodes have no identities and the number of nodes, say n, is the only known parameter of the network. After the randomized clustering, we show that the initialization problem can be solved in a multi-hop ad hoc wireless network of n stations in O(k ^1/2log ^1/2 k)+D _b −1+O(log (max (P _i )+log ²max (P _i )) broadcast rounds with high probability, where k is the number of clusters, D _b is the blocking diameter and max (P _i ), 1≤i≤k, is the maximum number of nodes in a cluster. Thus the initialization protocol presented here uses less broadcast rounds than the one in Ravelemanana (IEEE Trans. Parallel Distributed Syst. 18(1):17–28 2007).     

Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs

The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant ε > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size (ku, kl), our algorithm constructs a vertex cover of size (ku*, kl* ), satisfying max{ku*/ku, kl* /kl} 1 ε.     

Incremental Medians via Online Bidding

In the k-median problem we are given sets of facilities and customers, and distances between them. For a given set F of facilities, the cost of serving a customer u is the minimum distance between u and a facility in F. The goal is to find a set F of k facilities that minimizes the sum, over all customers, of their service costs. Following the work of Mettu and Plaxton, we study the incremental medians problem, where k is not known in advance. An incremental algorithm produces a nested sequence of facility sets F ₁⊆F ₂⊆⋅⋅⋅⊆F _n , where |F _k |=k for each k. Such an algorithm is called c -cost-competitive if the cost of each F _k is at most c times the optimum k-median cost. We give improved incremental algorithms for the metric version of this problem: an 8-cost-competitive deterministic algorithm, a 2e≈5.44-cost-competitive randomized algorithm, a (24+ε)-cost-competitive, polynomial-time deterministic algorithm, and a 6e+ε≈16.31-cost-competitive, polynomial-time randomized algorithm. We also consider the competitive ratio with respect to size. An algorithm is s -size-competitive if the cost of each F _k is at most the minimum cost of any set of k facilities, while the size of F _k is at most sk. We show that the optimal size-competitive ratios for this problem, in the deterministic and randomized cases, are 4 and e. For polynomial-time algorithms, we present the first polynomial-time O(log m)-size-approximation algorithm for the offline problem, as well as a polynomial-time O(log m)-size-competitive algorithm for the incremental problem. Our upper bound proofs reduce the incremental medians problem to the following online bidding problem: faced with some unknown threshold T∈ℝ⁺, an algorithm must submit “bids” b∈ℝ⁺ until it submits a bid b≥T, paying the sum of all its bids. We present folklore algorithms for online bidding and prove that they are optimally competitive. We extend some of the above results for incremental medians to approximately metric distance functions and to incremental fractional medians. Finally, we consider a restricted version of the incremental medians problem where k is restricted to one of two given values, for which we give a deterministic algorithm with a nearly optimal cost-competitive ratio. The conference version of this paper appeared in (Chrobak, M., et al. in Lecture Notes in Computer Science, vol. 3887, pp. 311–322, 2006). Research of M. Chrobak supported by NSF Grant CCR-0208856.     

New Linear-Time Algorithms for Edge-Coloring Planar Graphs

We show efficient algorithms for edge-coloring planar graphs. Our main result is a linear-time algorithm for coloring planar graphs with maximum degree Δ with max {Δ,9} colors. Thus the coloring is optimal for graphs with maximum degree Δ≥9. Moreover for Δ=4,5,6 we give linear-time algorithms that use Δ+2 colors. These results improve over the algorithms of Chrobak and Yung (J. Algorithms 10:35–51, 1989) and of Chrobak and Nishizeki (J. Algorithms 11:102–116, 1990) which color planar graphs using max {Δ,19} colors in linear time or using max {Δ,9} colors in time. R. Cole supported in part by NSF grants CCR0105678 and CCF0515127 and IDM0414763. Ł. Kowalik supported in part by KBN grant 4T11C04425. Part of this work was done while Ł. Kowalik was staying at the Max Planck Institute in Saarbruecken, Germany.     

Parallel batch scheduling of equal-length jobs with release and due dates

In this paper we study parallel batch scheduling problems with bounded batch capacity and equal-length jobs in a single and parallel machine environment. It is shown that the feasibility problem 1|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− can be solved in O(n ²) time and that the problem of minimizing the maximum lateness can be solved in O(n ²log n) time. For the parallel machine problem P|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− an O(n ³log n)-time algorithm is provided, which can also be used to solve the problem of minimizing the maximum lateness in O(n ³log ² n) time.     

A robust approach for the single machine scheduling problem

This paper describes a robust approach for the single machine scheduling problem 1|r _i |L _max. The method is said to be robust since it characterizes a large set of optimal solutions allowing to switch from one solution to another, without any performance loss, in order to face potential disruptions which occur during the schedule execution. It is based on a dominance theorem that characterizes a set of dominant sequences, using the interval structure defined by the relative order of the release and the due dates of jobs. The performance of a set of dominant sequences can be determined in polynomial time by computing the most favorable and the most unfavorable sequences associated with each job, with regard to the lateness criterion. A branch and bound procedure is proposed which modifies the interval structure of the problem in order to tighten the dominant set of sequences so that only the optimal sequences are conserved.     

Optimal External Memory Planar Point Enclosure

In this paper we study the external memory planar point enclosure problem: Given N axis-parallel rectangles in the plane, construct a data structure on disk (an index) such that all K rectangles containing a query point can be reported I/O-efficiently. This problem has important applications in e.g. spatial and temporal databases, and is dual to the important and well-studied orthogonal range searching problem. Surprisingly, despite the fact that the problem can be solved optimally in internal memory with linear space and O(log N+K) query time, we show that one cannot construct a linear sized external memory point enclosure data structure that can be used to answer a query in O(log  _B N+K/B) I/Os, where B is the disk block size. To obtain this bound, Ω(N/B ^1−ε ) disk blocks are needed for some constant ε>0. With linear space, the best obtainable query bound is O(log ₂ N+K/B) if a linear output term O(K/B) is desired. To show this we prove a general lower bound on the tradeoff between the size of the data structure and its query cost. We also develop a family of structures with matching space and query bounds. An extended abstract of this paper appeared in Proceedings of the 12th European Symposium on Algorithms (ESA’04), Bergen, Norway, September 2004, pp. 40–52. L. Arge’s research was supported in part by the National Science Foundation through RI grant EIA–9972879, CAREER grant CCR–9984099, ITR grant EIA–0112849, and U.S.-Germany Cooperative Research Program grant INT–0129182, as well as by the US Army Research Office through grant W911NF-04-01-0278, by an Ole Roemer Scholarship from the Danish National Science Research Council, a NABIIT grant from the Danish Strategic Research Council and by the Danish National Research Foundation. V. Samoladas’ research was supported in part by a grant co-funded by the European Social Fund and National Resources-EPEAEK II-PYTHAGORAS. K. Yi’s research was supported in part by the National Science Foundation through ITR grant EIA–0112849, U.S.-Germany Cooperative Research Program grant INT–0129182, and Hong Kong Direct Allocation Grant (DAG07/08).     

Tell Me Who I Am: An Interactive Recommendation System

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes or dislikes each object. However, the players do not know their preferences. To find his preference of an object, a player may probe it, but each probe incurs unit cost. The goal of the players is to learn their complete preference vector (approximately) while incurring minimal cost. This is possible if many players have similar preference vectors: such a set of players with similar “taste” may split the cost of probing all objects among them, and share the results of their probes by posting them on a public billboard. The problem is that players do not know a priori whose taste is close to theirs. In this paper we present a distributed randomized peer-to-peer algorithm in which each player outputs a vector which is close to the best possible approximation of the player’s real preference vector after a polylogarithmic number of rounds. The algorithm works under adversarial preferences. Previous algorithms either made severely limiting assumptions on the structure of the preference vectors, or had polynomial overhead. Research of N. Alon supported in part by the Israel Science Foundation and by the Von Neumann Fund. B. Awerbuch supported by NSF grants ANIR-0240551, CCF-0515080 and CCR-0311795. Research of Y. Azar supported in part by the German-Israeli Foundation and by the Israel Science Foundation. Research of B. Patt-Shamir supported in part by Israel Ministry of Science and Technology and by the Israel Science Foundation (grant 664/05).     

Energy-Efficient Paths in Radio Networks

We consider a radio network consisting of n stations represented as the complete graph on a set of n points in the Euclidean plane with edge weights ω(p,q)=|pq| ^δ +C _p , for some constant δ>1 and nonnegative offset costs C _p . Our goal is to find paths of minimal energy cost between any pair of points that do not use more than some given number k of hops.     

Algorithms for Modular Counting of Roots of Multivariate Polynomials

Given a multivariate polynomial P(X ₁,…,X _n ) over a finite field , let N(P) denote the number of roots over . The modular root counting problem is given a modulus r, to determine N _r (P)=N(P)mod r. We study the complexity of computing N _r (P), when the polynomial is given as a sum of monomials. We give an efficient algorithm to compute N _r (P) when the modulus r is a power of the characteristic of the field. We show that for all other moduli, the problem of computing N _r (P) is -hard. We present some hardness results which imply that our algorithm is essentially optimal for prime fields. We show an equivalence between maximum-likelihood decoding for Reed-Solomon codes and a root-finding problem for symmetric polynomials. P. Gopalan’s and R.J Lipton’s research was supported by NSF grant CCR-3606B64. V. Guruswami’s research was supported in part by NSF grant CCF-0343672 and a Sloan Research Fellowship.     

A New Efficient Algorithm for Computing the Longest Common Subsequence

The Longest Common Subsequence (LCS) problem is a classic and well-studied problem in computer science. The LCS problem is a common task in DNA sequence analysis with many applications to genetics and molecular biology. In this paper, we present a new and efficient algorithm for solving the LCS problem for two strings. Our algorithm runs in O(ℛlog log n+n) time, where ℛ is the total number of ordered pairs of positions at which the two strings match. Preliminary version appeared in [24]. C.S. Iliopoulos is supported by EPSRC and Royal Society grants. M.S. Rahman is supported by the Commonwealth Scholarship Commission in the UK under the Commonwealth Scholarship and Fellowship Plan (CSFP) and is on Leave from Department of CSE, BUET, Dhaka-1000, Bangladesh.     

Efficient Algorithms for the Riemann-Roch Problem and for Addition in the Jacobian of a Curve

We study the effective Riemann-Roch problem of computing a basis for the linear space L(D) associated with a divisor D on a plane curve C and its applications. Our presentation begins with an extension of Noether's algorithm for this problem to plane curves with singularities. Like the original, this algorithm has a worst-case complexity of Ω(n!^|D|), where n is the degree of the curve C.We next consider representations of divisors based on Chow forms. Using these, we produce a factorization-free polynomial-time algorithm for the effective Riemann-Roch problem, which improves the complexity of Noether's algorithm by an order of magnitude. We also present further improvements which, for curves of bounded degree, yield an algorithm with complexity which is linear in the size of the given divisor. Finally, we consider applications of this problem: to the arithmetic of the Jacobian of a plane curve, to the construction of rational functions on a curve with prescribed zeroes and poles, and to the construction of curves with prescribed intersections.     

Variable Sized Online Interval Coloring with Bandwidth

We consider online coloring of intervals with bandwidth in a setting where colors have variable capacities. Whenever the algorithm opens a new color, it must choose the capacity for that color and cannot change it later. A set of intervals can be assigned the same color a of capacity C _a if the sum of bandwidths of intervals at each point does not exceed C _a . The goal is to minimize the total capacity of all the colors used. We consider the bounded model, where all capacities must be chosen in the range (0,1], and the unbounded model, where the algorithm may use colors of any positive capacity. For the absolute competitive ratio, we give an upper bound of 14 and a lower bound of 4.59 for the bounded model, and an upper bound of 4 and a matching lower bound of 4 for the unbounded model. We also consider the offline version of these problems and show that whereas the unbounded model is polynomially solvable, the bounded model is NP-hard in the strong sense and admits a 3.6-approximation algorithm. A preliminary version of this paper has appeared in the Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), Lecture Notes in Computer Science, Vol. 4059, pp. 29–40, Springer, 2006.     

On Constrained Facility Location Problems

Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The k-Facility Location problem further requires that the number of opened facilities is at most k, where k is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant > 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 + ω + 1 + ε, which significantly improves the previous best known ratio (ω + 1)/α for some 1≤α≤2, and a polynomial-time approximation algorithm for the ω-constrained k- Facility Location problem with approximation ratio ω+1+ε. On the aspect of approximation hardness, we prove that unless NP■DTIME(nO(loglogn)), the ω-constrained Facility Location problem cannot be approximated within 1 + lnω - 1, which slightly improves the previous best known hardness result 1.243 + 0.316ln(ω - 1). The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.