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.     

The Minimum Range Assignment Problem on Linear Radio Networks

Abstract. Given a set S of radio stations located on a line and an integer h ≥ 1 , the MIN ASSIGNMENT problem consists in finding a range assignment of minimum power consumption provided that any pair of stations can communicate in at most h hops. Previous positive results for this problem are only known when h=|S|-1 or in the uniform chain case (i.e., when the stations are equally spaced). As for the first case, Kirousis et al. [7] provided a polynomial-time algorithm while, for the second case, they derive a polynomial-time approximation algorithm. This paper presents the first polynomial-time, approximation algorithm for the MIN ASSIGNMENT problem. The algorithm guarantees a 2-approximation ratio and runs in O(hn ³ ) time. We also prove that, for fixed h and for ``well spaced' instances (a broad generalization of the uniform chain case), the problem admits a polynomial-time approximation scheme . This result significantly improves over the approximability result given by Kirousis {et al}. Both our approximation results are obtained via new algorithms that exactly solve two natural variants of the MIN ASSIGNMENT problem: the problem in which every station must reach a fixed one in at most h hops and the problem in which the goal is to select a subset of bases such that all the other stations must reach one base in at most h-1 hops. Finally, we show that for h=2 the MIN ASSIGNMENT problem can be exactly solved in O(n ³ ) time.     

Random parallel algorithms for finding exact branchings,perfect matchings,and cycles

In this paper we devise randomized parallel algorithms which given a unary weighted (di)graphG=(V, E)construct in time O(log²¦ V¦) branchings, perfect matchings, and disjoint cycles of weightexactly k belonging toG. These problems have been studied by Papadimitriou and Yannakakis [PY1], by Barahona and Pulleyblank [BP], by Cameriniet al [CGM], and by Mulmuleyet al. [MVV]. Our algorithms improve previous solutions. Moreover, we give an NC² algorithm for computing the absolute value of the pfaffian of a skew-symmetric matrix.Supported in part by MURST 40%.     

Caching Documents with Variable Sizes and Fetching Costs: An LP-Based Approach

Abstract. We give an integer programming formulation of the paging problem with varying sizes and fetching costs. We use this formulation to provide an alternative proof that a variant of the algorithm greedy-dual-size previously considered in [4] and [5] is (k+1)/(k-h+1) competitive against the optimal strategy with cache size h≤ k . Our proof provides further insights to greedy-dual-size. We also indicate how the same integer programming formulation has been recently used [1], [2] to obtain approximation algorithms to the NP-complete ``offline' problem.     

Improved approximation algorithms for MAXk-CUT and MAX BISECTION

Polynomial-time approximation algorithms with nontrivial performance guarantees are presented for the problems of (a) partitioning the vertices of a weighted graph intok blocks so as to maximize the weight of crossing edges, and (b) partitioning the vertices of a weighted graph into two blocks of equal cardinality, again so as to maximize the weight of crossing edges. The approach, pioneered by Goemans and Williamson, is via a semidefinite programming relaxation. The first author was supported in part by NSF Grant CCR-9225008. The work described here was undertaken while the second author was visiting Carnegie Mellon University; at that time he was a Nuffield Science Research Fellow, and was supported in part by Grant GR/F 90363 of the UK Science and Engineering Research Council, and Esprit Working Group 7097 “RAND”.     

Randomized approximation of bounded multicovering problems

The problem of finding approximate solutions for a subclass of multicovering problems denoted byILP(k, b) is considered. The problem involves findingx∈{0,1} ⁿ that minimizes ∑ _j x _j subject to the constraintAx≥b, whereA is a 0–1m×n matrix with at mostk ones per row,b is an integer vector, andb is the smallest entry inb. This subclass includes, for example, the Bounded Set Cover problem whenb=1, and the Vertex Cover problem whenk=2 andb=1. An approximation ratio ofk−b+1 is achievable by known deterministic algorithms. A new randomized approximation algorithm is presented, with an approximation ratio of (k−b+1)(1−(c/m)^1/(k−b+1)) for a small constantc>0. The analysis of this algorithm relies on the use of a new bound on the sum of independent Bernoulli random variables, that is of interest in its own right. The first author was supported in part by a Walter and Elise Haas Career Development Award and by a grant from the Israeli Science Foundation. This work was done white the third author was at the Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel.     

One for the Price of Two: a Unified Approach for Approximating Covering Problems

We present a simple and unified approach for developing and analyzing approximation algorithms for covering problems. We illustrate this on approximation algorithms for the following problems: Vertex Cover, Set Cover, Feedback Vertex Set, Generalized Steiner Forest, and related problems. The main idea can be phrased as follows: iteratively, pay two dollars (at most) to reduce the total optimum by one dollar (at least), so the rate of payment is no more than twice the rate of the optimum reduction. This implies a total payment (i.e., approximation cost) ≤ twice the optimum cost. Our main contribution is based on a formal definition for covering problems, which includes all the above fundamental problems and others. We further extend the Bafna et al. extension of the Local-Ratio theorem. Our extension eventually yields a short generic r -approximation algorithm which can generate most known approximation algorithms for most covering problems. Another extension of the Local-Ratio theorem to randomized algorithms gives a simple proof of Pitt's randomized approximation for Vertex Cover. Using this approach, we develop a modified greedy algorithm, which for Vertex Cover gives an expected performance ratio ≤ 2 . Received September 17, 1997; revised March 5, 1998.     

Using Nondeterminism to Design Efficient Deterministic Algorithms

In this paper we illustrate how nondeterminism can be used conveniently and effectively in designing efficient deterministic algorithms. In particular, our method gives a parameterized algorithm of running time O((5.7 k)^k n) for the 3-D matching problem, which significantly improves the previous algorithm by Downey et al. The algorithm can be generalized to yield an improved algorithm for the r-D matching problem for any positive integer r. The method can also be employed in designing deterministic algorithms for other optimization problems as well.     

Polynomially Improved Efficiency for Fast Parallel Single-Source Lexicographic Depth-First Search, Breadth-First Search, and Topological-First Search

Although lexicographic (lex) variants of greedy algorithms are often P -complete, NC -algorithms are known for the following lex-search problems: lexicographic depth-first search (lex-dfs) for dags [12], [17], lexicographic breadth-first search (lex-bfs) for digraphs [12], [17], and lexicographic topological-first search (lex-tfs) for dags [12]. For the all-sources version of the problem for dense digraphs, the lex-dfs (lex-bfs, lex-tfs) in [12] is (within a log factor of) work-optimal with respect to the all-sources sequential solution that performs a dfs (bfs, tfs) from every vertex. By contrast, to solve the single-source lexicographic version on inputs of size n , all known NC -algorithms perform work that is at least an n factor away from the work performed by their sequential counterparts. We present parallel algorithms that solve the single-source version of these lex-search problems in O(log  ² n) time using M(n) processors on the EREW PRAM. (M(n) denotes the number of processors required to multiply two n\times n integer matrices in O(log  n) time and has O(n ^2.376 ) as tightest currently known bound.) They all offer a polynomial improvement in work-efficiency over that of their corresponding best previously known and close the gap between the requirements of the best known parallel algorithms for the lex and the nonlex versions of the problems. Key to the efficiency of these algorithms is the novel idea of a lex-splitting tree and lex-conquer subgraphs of a dag G from source s . These structures provide a divide-and-conquer skeleton from which NC -algorithms for several lexicographic search problems emerge, in particular, an algorithm that places in the class NC the lex-dfs for reducible flow graphs—an interesting class of graphs which arise naturally in connection with code optimization and data flow analysis [4], [19]. A notable aspect of these algorithms is that they solve the lex-search problem instance at hand by efficiently transforming solutions of appropriate instances of (nonlex) path problems. This renders them potentially capable of transferring significant algorithmic advances—such as Driscoll et al.'s [14] single-source shortest paths algorithm and Ullman and Yannakakis' [34] transitive closure algorithm—from fundamental (nonlex) path problems to lex-search problems. Received January 9, 1994, and in revised form November 1997. Online publication July 20, 2001.     

Asymmetric k-center with minimum coverage

In this paper we give approximation algorithms and inapproximability results for various asymmetric k-center with minimum coverage problems. In the k-center with minimum coverage problem, each center is required to serve a minimum number of clients. These problems have been studied by Lim et al. [A. Lim, B. Rodrigues, F. Wang, Z. Xu, k-center problems with minimum coverage, Theoret. Comput. Sci. 332 (1-3) (2005) 1-17] in the symmetric setting.     

Approximation algorithms for shop scheduling problems with minsum objective: A correction

We present a correction to the paper, “Approximation algorithms for shop scheduling problems with minsum objective” (Journal of Scheduling 2002; 5:287–305) by Queyranne and Sviridenko. This correction provides a correct derivation of its 2eρ approximation result. Wenhua Li and Jinjiang Yuan: Project supported by NNSFC (Grant 10371112) and NSFHN (Grant 0411011200). Maurice Queyranne: Supported by research grants from NSERC, the Natural Sciences and Engineering Research Council of Canada.     

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n ⁵) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n ¹¹) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong.     

Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks

Abstract. A malleable parallel task is one whose execution time is a function of the number of (identical) processors alloted to it. We study the problem of scheduling a set of n independent malleable tasks on a fixed number of parallel processors, and propose an approximation scheme that for any fixed ε > 0 , computes in O(n) time a non-preemptive schedule of length at most (1+ε) times the optimum.     

An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs

Given a positive integer k and a complete graph with non-negative edge weights satisfying the triangle inequality, the remote-clique problem is to find a subset of k vertices having a maximum-weight induced subgraph. A greedy algorithm for the problem has been shown to have an approximation ratio of 4, but this analysis was not shown to be tight. In this paper, we use the technique of factor-revealing linear programs to show that the greedy algorithm actually achieves an approximation ratio of 2, which is tight. This research was supported in part by the National Science Foundation under grant CISE-EI-0305954 and was performed while the first author was at Washington University in St. Louis. A preliminary version of this paper appears in RANDOM-APPROX ’06, volume 4110 of Lecture Notes in Computer Science, pp. 49–60, 2006.     

Solving Some Discrepancy Problems in NC

We show that several discrepancy-like problems can be solved in NC nearly achieving the discrepancies guaranteed by a probabilistic analysis and achievable sequentially. For example, we describe an NC algorithm that given a set system (X, S) , where X is a ground set and S⊆2 ^X , computes a set R⊆X so that for each S∈ S the discrepancy ||R S|-|R^-∩S|| is . Whereas previous NC algorithms could only achieve discrepancies with ɛ>0 , ours matches the probabilistic bound within a multiplicative factor 1+o(1) . Other problems whose NC solution we improve are lattice approximation, ɛ -approximations of range spaces with constant VC-exponent, sampling in geometric configuration spaces, approximation of integer linear programs, and edge coloring of graphs. Received June 26, 1998; revised February 18, 1999.     

The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem

Several classes of sequential algorithms to approximate themaximum acyclic subgraph problem are examined. The equivalentfeedback arc set problem isNP-complete and there are only a few classes of graphs for which it is known to be inP. Thus, approximation algorithms are very important for this problem. Our goal is to determine how effectively the various sequential algorithms parallelize. Of the sequential algorithms we study, natural decision problems based on several of them are provedP-complete. Parallel implementations usingO(log ¦V¦) time and ¦E¦ processors on an EREW PRAM exist for the other algorithms. Interestingly, the parallelizable algorithms appear very similar to some of theinherently sequential algorithms. Thus, for approximating the maximum acyclic subgraph problem small algorithmic changes drastically alter parallel complexity, unlessNC equalsP.     

Approximation Algorithms for Multi-Criteria Traveling Salesman Problems

We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with γ-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of and a randomized approximation algorithm that achieves a ratio of . In particular, we obtain a 2+ε approximation for multi-criteria metric STSP. Then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximation algorithms for STSP with γ-triangle inequality (ratio ), asymmetric TSP (ATSP) with γ-triangle inequality (ratio ), STSP with weights one and two (ratio 4/3) and ATSP with weights one and two (ratio 3/2). A preliminary version of this work has been presented at the 4th Workshop on Approximation and Online Algorithms (WAOA 2006) (Lecture Notes in Computer Science, vol. 4368, pp. 302–315, 2007). B. Manthey is supported by the Postdoc-Program of the German Academic Exchange Service (DAAD). He is on leave from Saarland University and has done part of the work at the Institute for Theoretical Computer Science of the University of Lübeck supported by DFG research grant RE 672/3 and at the Department of Computer Science at Saarland University.     

Augmenting Trees to Meet Biconnectivity and Diameter Constraints

Given a graph G=(V,E) and a positive integer D , we consider the problem of finding a minimum number of new edges E' such that the augmented graph G'=(V,E\cup E') is biconnected and has diameter no greater than D. In this note we show that this problem is NP-hard for all fixed D , by employing a reduction from the DOMINATING SET problem. We prove that the problem remains NP-hard even for forests and trees, but in this case we present approximation algorithms with worst-case bounds 3 (for even D ) and 6 (for odd D ). A closely related problem of finding a minimum number of edges such that the augmented graph has diameter no greater than D has been shown to be NP-hard by Schoone et al. [21] when D=3 , and by Li et al. [17] when D=2. Received April 19, 1999; revised June 5, 2001.     

Optimal geometric algorithms for digitized images on fixed-size linear arrays and scan-line arrays

Summary Linear arrays are characterized by a small communication bandwidth and a large communication diameter rendering them unsuited to the implementation of global computations. This paper presents efficient data movement and partitioning techniques to overcome several shortcomings of linear arrays. These techniques are used to derive optimal parallel algorithms for several geometric problems onn×n images using a fixed-size linear array withp processors, where 1pn.O(n ²/p) time solutions are presented for labeling connected image regions, computing the convex hull of each region, and computing nearest neighbors. Consequently, a linear array withn processors can solve several image problems inO(n) time which is the same time taken by a two dimensional mesh-connected computer withn ² processors. Limitations of linear arrays are analyzed by presenting a class of image problems which can be solved sequentially inO(n) ² ) time, but require (n ²) time on a linear array, irrespective of the number of processors used and the partitioning of the input image among the processors. An alternate communication-efficient fixed-size organization withp processors is proposed to solve such problems inO(n ²/p) time, for 1pn. Hussein M. Alnuweiri received the B.S. and M.S. degrees in 1983 and 1984, respectively, both in electrical engineering from King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia, and received the Ph.D. degree also in electrical engineering in 1989 from the University of Southern California, Los Angeles. Currently he is an assistant professor in the electrical engineering department at University of British Columbia. His research interests include parallel architectures and algorithms, computational aspects of VLSI networks, complexity of parallel computations, and algorithmic aspects of image analysis, vision, and robot motion planning. Viktor K. Prasanna (V. K. Prasanna Kumar) received his BS in Electronics Engineering from the Bangalore University, his MS from the School of Automation, Indian Institute of Science. He obtained his Ph.D. in Computer Science from Pennsylvania State University in 1983. Currently, he is an Associate Professor in the department of Electrical Engineering-Systems, University of Southern California, Los Angeles. His current research interests include Parallel Computation, Computer Architecture, VLSI Computations and Computational aspects of Image Processing and Vision. He is the editor of the book Parallel Architectures and Algorithms for Image understanding published by Academic Press. Professor Prasanna serves on number of international committees and panels and is a consultant for several industries. He is the program chair of the 1992 International Parallel Processing Symposium sponsored by IEEE Computer Society and is a subject area editor of Journal of Parallel and Distributed Computing.This research was supported in part by the National Science Foundation under grant IRI-8710836 and in part by DARPA under contract F 33615-87-C-1436 monitored by Wright Patterson Airforce Base. A preliminary version of this paper appears in the IEEE Conference on Computer Vision and Pattern Recognition, 1988.     

Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs

In this paper we consider the p-ary transitive reduction (TR _p ) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. Special cases of TR _p have been investigated before in different contexts; the best previous results are as follows: