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.     

Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.     

Practical Methods for Shape Fitting and Kinetic Data Structures using Coresets

The notion of ε-kernel was introduced by Agarwal et al. (J. ACM 51:606–635, 2004) to set up a unified framework for computing various extent measures of a point set P approximately. Roughly speaking, a subset Q⊆P is an ε-kernel of P if for every slab W containing Q, the expanded slab (1+ε)W contains P. They illustrated the significance of ε-kernel by showing that it yields approximation algorithms for a wide range of geometric optimization problems. We present a simpler and more practical algorithm for computing the ε-kernel of a set P of points in ℝ ^d . We demonstrate the practicality of our algorithm by showing its empirical performance on various inputs. We then describe an incremental algorithm for fitting various shapes and use the ideas of our algorithm for computing ε-kernels to analyze the performance of this algorithm. We illustrate the versatility and practicality of this technique by implementing approximation algorithms for minimum enclosing cylinder, minimum-volume bounding box, and minimum-width annulus. Finally, we show that ε-kernels can be effectively used to expedite the algorithms for maintaining extents of moving points. A preliminary version of the paper appeared in Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 2004, pp. 263–272. Research by the first two authors is supported by NSF under grants CCR-00-86013, EIA-98-70724, EIA-01-31905, and CCR-02-04118, and by a grant from the US–Israel Binational Science Foundation. Research by the fourth author is supported by NSF CAREER award CCR-0237431.     

Distributed reconfiguration of metamorphic robot chains

The problem we address is the distributed reconfiguration of a planar metamorphic robotic system composed of any number of hexagonal modules. After presenting a framework for classifying motion planning algorithms for metamorphic robotic systems, we describe distributed algorithms for reconfiguring a straight chain of hexagonal modules to any intersecting straight chain configuration. We prove our algorithms are correct, and show that they are either optimal or asymptotically optimal in the number of moves and asymptotically optimal in the time required for parallel reconfiguration.Received: 28 October 2002, Accepted: 31 October 2003, Published online: 1 March 2004 Corresdpondence to: Jennifer E. WalterNancy M. Amato: amato]@cs.tamu.edu A preliminary version of this paper appeared in the Proc. of the 19th ACM Symposium on Principles of Distributed Computing, July 2000, pages 171-180. The work of N. Amato and J. Walter was supported in part by NSF CAREER Award CCR-9624315, NSF Grants IIS-9619850, ACI-9872126, EIA-9975018, EIA-0103742, EIA-9805823, ACR-0081510, ACR-0113971, CCR-0113974, EIA-9810937, EIA-0079874, by the Texas Higher Education Coordinating Board grant ARP-036327-017, and by the DOE ASCI ASAP program grant B347886. The work of J. Walter was supported in part by Department of Education GAANN and GE Faculty of the Future fellowships.     

Partial Bi-immunity,Scaled Dimension,and NP-Completeness

The Turing and many-one completeness notions for NP have been previously separated under measure, genericity, and bi-immunity hypotheses on NP. The proofs of all these results rely on the existence of a language in NP with almost everywhere hardness. In this paper we separate the same NP-completeness notions under a partial bi-immunity hypothesis that is weaker and only yields a language in NP that is hard to solve on most strings. This improves the results of Lutz and Mayordomo (Theoretical Computer Science, 1996), Ambos-Spies and Bentzien (Journal of Computer and System Sciences, 2000), and Pavan and Selman (Information and Computation, 2004). The proof of this theorem is a significant departure from previous work. We also use this theorem to separate the NP-completeness notions under a scaled dimension hypothesis on NP. Part of this research was done while J.M. Hitchcock was visiting the University of Nebraska-Lincoln. Research of J.M. Hitchcock supported in part by NSF grant CCF-0515313. Research of A. Pavan supported in part by NSF grants CCR-0344187 and CCF-0430807. Research of N.V. Vinodchandran supported in part by NSF grant CCF-0430991 and University of Nebraska Layman Award.     

Combinatorial Algorithms for Data Migration to Minimize Average Completion Time

The data migration problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. It is modeled by a transfer graph, where vertices represent the storage devices, and edges represent data transfers required between pairs of devices. Each vertex has a non-negative weight, and each edge has a processing time. A vertex completes when all the edges incident on it complete; the constraint is that two edges incident on the same vertex cannot be processed simultaneously. The objective is to minimize the sum of weighted completion times of all vertices. Kim (J. Algorithms 55, 42–57, 2005) gave an LP-rounding 3-approximation algorithm when edges have unit processing times. We give a more efficient primal-dual algorithm that achieves the same approximation guarantee. When edges have arbitrary processing times we give a primal-dual 5.83-approximation algorithm. We also study a variant of the open shop scheduling problem. This is a special case of the data migration problem in which the transfer graph is bipartite and the objective is to minimize the sum of completion times of edges. We present a simple algorithm that achieves an approximation ratio of , thus improving the 1.796-approximation given by Gandhi et al. (ACM Trans. Algorithms 2(1), 116–129, 2006). We show that the analysis of our algorithm is almost tight. A preliminary version of the paper appeared in the Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006. Research of R. Gandhi partially supported by Rutgers University Research Council Grant. Research of J. Mestre done at the University of Maryland; supported by NSF Awards CCR-0113192 and CCF-0430650, and the University of Maryland Dean’s Dissertation Fellowship.     

Checking extended <Emphasis Type="Italic">CTL</Emphasis> properties using guarded quotient structures

We extend CTL logic to a logic called COUNT CTL (CCTL) for specifying properties of concurrent programs with large number of processes. We present a model checking algorithm for symmetric or partially symmetric systems when their correctness specification is given in CCTL. The model-checking algorithm employs Guarded Quotient Structures introduced by Sistla and Godefroid (Lecture Notes in Comput. Sci., vol. 2102, 2001). The GQS structures can be succinct representations for the reachability graphs of partially symmetric or even asymmetric systems. Our algorithm exploits state symmetries for fast evaluation. The algorithm is top down in nature, and automatically incorporates formula decomposition and sub-formula tracking. This paper is supported in part by the NSF grants CCR-9988884, CCR-0205365.     

A network pricing game for selfish traffic

The success of the Internet is remarkable in light of the decentralized manner in which it is designed and operated. Unlike small scale networks, the Internet is built and controlled by a large number of disparate service providers who are not interested in any global optimization. Instead, providers simply seek to maximize their own profit by charging users for access to their service. Users themselves also behave selfishly, optimizing over price and quality of service. Game theory provides a natural framework for the study of such a situation. However, recent work in this area tends to focus on either the service providers or the network users, but not both. This paper introduces a new model for exploring the interaction of these two elements, in which network managers compete for users via prices and the quality of service provided. We study the extent to which competition between service providers hurts the overall social utility of the system. A preliminary version of this paper appeared in the proceedings of 24th annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, July 17–20, 2005, Las Vegas, Nevada, USA. The work of Ara Hayrapetyan was supported in part by NSF ITR grant CCR-0325453. The work of éva Tardos was supported in part by NSF grant CCR-0311333, ITR grant CCR-0325453, and ONR grant N00014-98-1-0589. The work of Tom Wexler was supported in part by NSF ITR grant CCR-0325453.     

Constructing the Voronoi diagram of a set of line segments in parallel

In this paper we give a parallel algorithm for constructing the Voronoi diagram of a polygonal scene, i.e., a set of line segments in the plane such that no two segments intersect except possibly at their endpoints. Our algorithm runs inO(log² n) time usingO(n) processors in the CREW PRAM model.The research of M. T. Goodrich was supported by NSF under Grants CCR-8810568 and CCR-9003299 and by NSF/DARPA under Grant CCR-8908092. C. K. Yap's research was supported in part by NSF Grants DCR-8401898 and CCR-9002819.     

Efficient distributed algorithms for single-source shortest paths and related problems on plane networks

An efficient distributed algorithm is given for computing single-source shortest paths in an asynchronous planar network. The algorithm has message and time complexityO(pn) on ann-node network, wherep is the smallest number of faces needed to cover all the nodes, taken over all possible plane embeddings of the network. Each node has only local information about the network, consisting of an ordered list of its incident edges in the embedding that realizesp and the name of the covering face that it belongs to. The complexity of the algorithm ranges fromO(n) toO(n ²) asp ranges from 1 to Θ(n). The algorithm is more efficient than previous algorithms [A3], [F1] for a broad range of values forp; however, the algorithms in [A3] and [F1] do not require knowledge about the embedding. The single-source algorithm incorporates optimal distributed solutions to a number of interesting subproblems including: (i) decomposing the plane embedding into Θ(p) outerplane graphs with favorable properties; (ii) a single-source algorithm for outerplane graphs; and (iii) identifying any edge in an outerplane graph whose cost exceeds the distance between its endpoints. As an application, a communication-, time-, and space-efficient message-routing scheme is presented which adapts to changing link conditions and routes along near-shortest paths. This research was supported in part by a grant-in-aid of research from the Graduate School of the University of Minnesota. R. Janardan was also supported in part by NSF Grant CCR-8808574. Portions of this work were presented at the 4th International Workshop on Distributed Algorithms, Bari, Italy, September 1990.     

An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs

We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takesO(log² n) time withO(n ³) processors on a CREW PRAM, wheren is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.Research supported in part by NSF Grants CCR-9011214 and CCR-9205982.     

Primitives for asynchronous list compression

In this paper we study the problem of asynchronous processors traversing a list with path compression. We show that if an atomic splice operation is available, the worst-case work forp processors traversing a list of length h is (np ^1/2). The splice operation can be generalized to removek elements from the list. For thek-splice operation the worst-case work is (np ^1/ k+1).This research was supported by an NSF Presidential Young Investigator Award CCR-8657562, Digital Equipment Corporation, NSF CER Grant CCR-861966, and NSF/Darpa Grant CCR-8907960. A preliminary version of this paper was presented at the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures.     

Parallel algorithms for arrangements

We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log^* n) time andn ²/logn processors. We generalize this to obtain anO (logn log^* n)-time algorithm usingn ^d /logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn/logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.This work was supported by the National Science Foundation, under Grants CCR-8657562 and CCR-8858799, NSF/DARPA under Grant CCR-8907960, and Digital Equipment Corporation. A preliminary version of this paper appeared at the Second Annual ACM Symposium on Parallel Algorithms and Architectures [3].     

Random Bichromatic Matchings

Given a graph with edges colored Red and Blue, we study the problem of sampling and approximately counting the number of matchings with exactly k Red edges. We solve the problem of estimating the number of perfect matchings with exactly k Red edges for dense graphs. We study a Markov chain on the space of all matchings of a graph that favors matchings with k Red edges. We show that it is rapidly mixing using non-traditional canonical paths that can backtrack. We show that this chain can be used to sample matchings in the 2-dimensional toroidal lattice of any fixed size ℓ with k Red edges, where the horizontal edges are Red and the vertical edges are Blue. An extended abstract appeared in J.R. Correa, A. Hevia and M.A. Kiwi (eds.) Proceedings of the 7th Latin American Theoretical Informatics Symposium, LNCS 3887, pp. 190–201, Springer, 2006. N. Bhatnagar’s and D. Randall’s research was supported in part by NSF grants CCR-0515105 and DMS-0505505. V.V. Vazirani’s research was supported in part by NSF grants 0311541, 0220343 and CCR-0515186. N. Bhatnagar’s and E. Vigoda’s research was supported in part by NSF grant CCR-0455666.     

A bounded approximation for the minimum cost 2-sat problem

Given a satisfiable Boolean formula in 2-CNF, it is NP-hard to find a satisfying assignment that contains a minimum number of true variables. A polynomial-time approximation algorithm is given that finds an assignment with at most twice as many true variables as necessary. The algorithm also works for a weighted generalization of the problem. An application to the optimal stable roommates problem is given in detail, and other applications are mentioned.D. Gusfield was supported in part by NSF Grant CCR-8803704. Part of this work was done while he was at Yale University, partially supported by NSF Grant MCS-8105894. L. Pitt was supported in part by NSF Grant IRI-8809570. Part of this work was done while he was at Yale University, supported by NSF Grants MCS-8002447, MCS-8116678, and MCS-8204246.     

Simulating BPP using a general weak random source

We show how to simulate BPP and approximation algorithms in polynomial time using the output from a -source. A -source is a weak random source that is asked only once forR bits, and must output anR-bit string according to some distribution that places probability no more than 2^–R on any particular string. We also give an application to the unapproximability of MAX CLIQUE.This paper appeared in preliminary form in theProceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991, pp. 79–89. Most of this research was done while the author was at U.C. Berkeley, and supported by an AT&T Graduate Fellowship, NSF PYI Grant No. CCR-8896202, and NSF Grant No. IRI-8902813. Part of this research was done while the author was at MIT, supported by an NSF Postdoctoral Fellowship, NSF Grant No. 92-12184 CCR, and DARPA Grant No. N00014-92-J-1799. Part of this research was done at UT Austin, where the author was supported by NSF NYI Grant No. CCR-9457799.     

Randomized competitive algorithms for the list update problem

We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.A preliminary version of these results appeared in a joint paper with S. Irani in theProceedings of the 2nd Symposium on Discrete Algorithms, 1991 [17].This research was partially supported by NSF Grants CCR-8808949 and CCR-8958528.This research was partially supported by NSF Grant CCR-9009753.This research was supported in part by the National Science Foundation under Grant CCR-8658139, by DIMACS, a National Science Foundation Science and Technology center, Grant No. NSF-STC88-09648.     

Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors

We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n ² log n) toO(n log² n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.     

An efficient parallel algorithm for finding rectangular duals of plane triangular graphs

We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takesO(log² n) time withO(n) processors on a CRCW PRAM, wheren is the number of vertices of the graph.This research was supported by NSF Grants CCR-9011214 and CCR-9205982.     

A time-optimal parallel algorithm for three-dimensional convex hulls

In this paper we present an O(1/ logn)-time parallel algorithm for computing the convex hull ofn points in ³. This algorithm usesO(@#@ n^1+a) processors on a CREW PRAM, for any constant 0 < 1. So far, all adequately documented parallel algorithms proposed for this problem use time at least O(log² n). In addition, the algorithm presented here is the first parallel algorithm for the three-dimensional convex hull problem that is not based on the serial divide-and-conquer algorithm of Preparata and Hong, whose crucial operation is the merging of the convex hulls of two linearly separated point sets. The contributions of this paper are therefore (i) an O(logn)-time parallel algorithm for the three-dimensional convex hull problem, and (ii) a parallel algorithm for this problem that does not follow the traditional paradigm.This paper was presented in preliminary form at the 9th Annual ACM Symposium on Computational Geometry, San Diego, CA, May 1993 [32]. The work of N. M. Amato was supported in part by an AT&T Bell Laboratories Graduate Fellowship, the Joint Services Electronics Program (U.S. Army, U.S. Navy, U.S. Air Force) under Contract N00014-90-J-1270, and NSF Grant CCR-89-22008. This work was done while N. M. Amato was with the Department of Computer Science at the University of Illinois. The work of F. P. Preparata was supported in part by NSF Grants CCR-91-96152, CCR-91-96176, and ONR Contract N00014-91-J-4052, ARPA order 8225.