Search

Abstract: Let be a compact, smooth, connected, Riemannian manifold without boundary, be a kernel. Analogous to a radial basis function network, an eignet is an expression of the form , where , , . We describe a deterministic, universal algorithm for constructing an eignet for approximating functions in for a general class of measures μ and kernels G. Our algorithm yields linear operators. Using the minimal separation among the centers as the cost of approximation, we give modulus of smoothness estimates for the degree of approximation by our eignets, and show by means of a converse theorem that these are the best possible for every individual function. We also give estimates on the coefficients in terms of the norm of the eignet. Finally, we demonstrate that if any sequence of eignets satisfies the optimal estimates for the degree of approximation of a smooth function, measured in terms of the minimal separation, then the derivatives of the eignets also approximate the corresponding derivatives of the target function in an optimal manner. [Copyright &y& Elsevier]

Abstract: We give a trichotomy theorem for the complexity of approximately counting the number of satisfying assignments of a Boolean CSP instance. Such problems are parameterised by a constraint language specifying the relations that may be used in constraints. If every relation in the constraint language is affine then the number of satisfying assignments can be exactly counted in polynomial time. Otherwise, if every relation in the constraint language is in the co-clone from Post''s lattice, then the problem of counting satisfying assignments is complete with respect to approximation-preserving reductions for the complexity class . This means that the problem of approximately counting satisfying assignments of such a CSP instance is equivalent in complexity to several other known counting problems, including the problem of approximately counting the number of independent sets in a bipartite graph. For every other fixed constraint language, the problem is complete for #P with respect to approximation-preserving reductions, meaning that there is no fully polynomial randomised approximation scheme for counting satisfying assignments unless NP=RP. [Copyright &y& Elsevier]

Abstract: We develop an algorithmically useful refinement of a forbidden submatrix characterization of 0/1-matrices fulfilling the Consecutive Ones Property (C1P). This characterization finds applications in new polynomial-time approximation algorithms and fixed-parameter tractability results for the NP-hard problem to delete a minimum number of rows or columns from a 0/1-matrix such that the remaining submatrix has the C1P. [Copyright &y& Elsevier]

Abstract: For more and more applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. This paper gives an overview of several upper bound heuristics that have been proposed and tested for the problem of determining the treewidth of a graph and finding tree decompositions. Each of the heuristics produces tree decompositions whose width may be larger than the optimal width. However, experiments show that in many cases, the heuristics give tree decompositions whose width is close to the exact treewidth of the input graphs. [Copyright &y& Elsevier]

Abstract: SONET add-drop multiplexers (ADMs) are the dominant cost factor in SONET/WDM rings. The number of SONET ADMs required by a set of traffic streams is determined by the routing and wavelength assignment of the traffic streams. Following previous work, we consider the problem where the route of each traffic stream is given as input, and we need to assign wavelengths so as to minimize the total number of used SONET ADMs. This problem is known to be NP-hard, and the best known approximation algorithm for this problem has a performance guarantee of . We improve this result, and present a -approximation algorithm. We also study some of the previously proposed algorithms for this problem, and give either tight or tighter analysis of their approximation ratio. [Copyright &y& Elsevier]

Abstract: When attempting to design a truthful mechanism for a computationally hard problem such as combinatorial auctions, one is faced with the problem that most efficiently computable heuristics can not be embedded in any truthful mechanism (e.g. VCG-like payment rules will not ensure truthfulness). We develop a set of techniques that allow constructing efficiently computable truthful mechanisms for combinatorial auctions in the special case where each bidder desires a specific known subset of items and only the valuation is unknown by the mechanism (the single parameter case). For this case we extend the work of Lehmann, O''Callaghan, and Shoham, who presented greedy heuristics. We show how to use If-Then-Else constructs, perform a partial search, and use the LP relaxation. We apply these techniques for several canonical types of combinatorial auctions, obtaining truthful mechanisms with provable approximation ratios. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of covering a set of strings S with a set C of substrings in S, where C is said to cover S if every string in S can be written as a concatenation of the substrings in C. We discuss applications for the problem that arise in the context of computational biology and formal language theory. We then proceed to show several hardness of approximation results for the problem, and in the main part of the paper, we focus on devising approximation algorithms using two generic paradigms—the local-ratio technique and linear programming rounding. [Copyright &y& Elsevier]

Abstract: We study the problem of scheduling transmissions on the downlink of IEEE 802.16/WiMAX systems that use the OFDMA technology. These transmissions are scheduled using a matrix whose dimensions are frequency and time, where every matrix cell is a time slot on some carrier channel. The IEEE 802.16 standard mandates that: (i) every transmission occupies a rectangular set of cells, and (ii) transmissions must be scheduled according to a given order. We show that if the number of cells required by a transmission is not limited (up to the matrix size), the problem of maximizing matrix utilization is very hard to approximate. On the positive side we show that if the number of cells of every transmission is limited to some constant fraction of the matrix area, the problem can be approximated to within a constant factor. As far as we know this is the first paper that considers this sequential rectangle placement problem. [Copyright &y& Elsevier]

Enhancement of remotely sensed images is a challenging problem, since the enhanced image has to have an improved contrast and edge information while preserving the original radiance values as much as possible. In this paper, a scale aware enhancement method based on rolling guidance is proposed for remotely sensed images. For each scale, a guidance image is defined and the approximation image is provided by an iterative joint filtering of the approximation and guidance images. Then the extracted details are amplified through an adaptive scheme and added to the final level approximation layer to provide the resulting enhanced image. A comparative study between the proposed methods with classical edge preserving filters and traditional methods have been carried out by using several criteria. The proposed methods have an average of 12% improvement for contrast gain (CG) metric and 81% improvement for enhancement measurement (EME) metric compared to the closest comparison method. • A remote sensing scale-aware image enhancement method is proposed. • A multiscale decomposition scheme based on rolling guidance is developed. • The images are enhanced by weighting the detail layers in the reconstruction step. • An adaptive weighting scheme is proposed to provide a better local enhancement. • The proposed method has better enhancement, while preserving spectral content. [ABSTRACT FROM AUTHOR]

Abstract: In many economic settings, like spectrum and real-estate auctions, geometric figures on the plane are for sale. Each bidder bids for his desired figure, and the auctioneer has to choose a set of disjoint figures that maximizes the social welfare. In this work, we design mechanisms that are both incentive compatible and computationally feasible for these environments. Since the underlying algorithmic problem is computationally hard, these mechanisms cannot always achieve the optimal welfare; Nevertheless, they do guarantee a fraction of the optimal solution. We differentiate between two information models—when both the desired figures and their values are unknown to the auctioneer or when only the agents'' values are private data. We guarantee different fractions of the optimal welfare for each information model and for different families of figures (e.g., arbitrary convex figures or axis-aligned rectangles). We suggest using a measure on the geometric diversity of the figures for expressing the quality of the approximations that our mechanisms provide. [Copyright &y& Elsevier]

Abstract: Fischer proposes in [T. Fischer, Optimizing the degree of minimum weight spanning trees, Technical Report 93–1338, Department of Computer Science, Cornell University, Ithaca, NY, USA, 1993] a sequential algorithm to compute a minimum weight spanning tree of maximum degree at most in time for any constant , where is the maximum degree value of an optimal solution and n is the number of nodes in the network. In the present paper, we propose a distributed version of Fischer''s sequential algorithm with time complexity , requiring messages and space per node, where is the maximum degree of an initial minimum weight spanning tree. [Copyright &y& Elsevier]

Abstract: We propose a new approximation technique for Hybrid Automata. Given any Hybrid Automaton H, we call Approx(H, k) the Polynomial Hybrid Automaton obtained by approximating each formula ϕ in H with the formulae ϕ k obtained by replacing the functions in ϕ with their Taylor polynomial of degree k. We prove that Approx(H, k) is an over-approximation of H. We study the conditions ensuring that, given any ϵ >0, some k 0 exists such that, for all k > k 0, the “distance” between any vector satisfying ϕ k and at least one vector satisfying ϕ is less than ϵ. We study also conditions ensuring that, given any ϵ >0, some k 0 exists such that, for all k > k 0, the “distance” between any configuration reached by Approx(H, k) in n steps and at least one configuration reached by H in n steps is less than ϵ. [Copyright &y& Elsevier]

Abstract: A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring of trees arises in areas such as phylogenetics, linguistics, etc., e.g., a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree. Research on perfect phylogeny is usually focused on finding a tree so that few predetermined partial colorings of its vertices are convex. When a coloring of a tree is not convex, it is desirable to know “how far” it is from a convex one. In [S. Moran, S. Snir, Convex recoloring of strings and trees: Definitions, hardness results and algorithms, in: WADS, 2005, pp. 218–232; J. Comput. System Sci., submitted for publication], a natural measure for this distance, called the recoloring distance was defined: the minimal number of color changes at the vertices needed to make the coloring convex. This can be viewed as minimizing the number of “exceptional vertices” w.r.t. a closest convex coloring. The problem was proved to be NP-hard even for colored strings. In this paper we continue the work of [S. Moran, S. Snir, Convex recoloring of strings and trees: Definitions, hardness results and algorithms, in: WADS, 2005, pp. 218–232; J. Comput. System Sci., submitted for publication], and present a 2-approximation algorithm of convex recoloring of strings whose running time , where c is the number of colors and n is the size of the input, and an 3-approximation algorithm for convex recoloring of trees. [Copyright &y& Elsevier]

Abstract: We consider the problem of optimizing the total flow time of a stream of jobs that are released over time in a multiprocessor setting. This problem is NP-hard even when there are only two machines and preemption is allowed. Although the total (or average) flow time is widely accepted as a good measurement of the overall quality of service, no approximation algorithms were known for this basic scheduling problem. This paper contains two main results. We first prove that when preemption is allowed, Shortest Remaining Processing Time (SRPT) is an approximation algorithm for the total flow time, where n is the number of jobs, m is the number of machines, and P is the ratio between the maximum and the minimum processing time of a job. We also provide an lower bound on the (worst case) competitive ratio of any randomized algorithm for the on-line problem in which jobs are known at their release times. Thus, we show that up to a constant factor SRPT is an optimal on-line algorithm. Our second main result addresses the non-preemptive case. We present a general technique that allows to transform any preemptive solution into a non-preemptive solution at the expense of an factor in the approximation ratio of the total flow time. Combining this technique with our previous result yields an approximation algorithm for this case. We also show an lower bound on the approximability of this problem (assuming ). [Copyright &y& Elsevier]

Abstract: We study the problem of scheduling unit size jobs on n processors connected by a ring. We show a distributed algorithm for this problem with an approximation ratio of . [Copyright &y& Elsevier]

Abstract: Let S be a set of n points in the plane. We derive algorithms for approximating S by a step function of size k < n, i.e., by an x-monotone rectilinear polyline with k < n horizontal segments. We use the vertical distance to measure the quality of the approximation, i.e., the maximum distance from a point in S to the horizontal segment directly above or below it. We consider two types of problems: min-ε, where the goal is to minimize the error for a given number of horizontal segments k and min-#, where the goal is to minimize the number of segments for a given allowed error ε. After O (n) preprocessing time, we solve instances of the latter in O (min{k log n, n}) time per instance. We can then solve the former problem in O (min{n 2, nk log n}) time. Both algorithms require O (n) space. Our second contribution is an approximation algorithm for the min-ε problem that computes a solution within a factor of 3 of the optimal error for k segments, or with at most the same error as the k-optimal but using 2k −1 segments. Furthermore, experiments on real data show even better results than what is guaranteed by the theoretical bounds. Both approximations run in O (n log n) time and O (n) space. [Copyright &y& Elsevier]

Abstract: The effectiveness of a distributed system hinges on the manner in which tasks and data are assigned to the underlying system resources. Moreover, today''s large-scale distributed systems must accommodate heterogeneity in both the offered load and in the makeup of the available storage and compute capacity. The ideal resource assignment must balance the utilization of the underlying system against the loss of locality incurred when individual tasks or data objects are fragmented among several servers. In this paper we describe this locality-maximizing placement problem and show that an optimal solution is NP-hard. We then describe a polynomial-time algorithm that generates a placement within an additive constant of two from optimal. [Copyright &y& Elsevier]

Abstract: We consider a directed network in which every edge possesses a latency function that specifies the time needed to traverse the edge given its congestion. Selfish, noncooperative agents constitute the network traffic and wish to travel from a source vertex s to a destination t as quickly as possible. Since the route chosen by one network user affects the congestion experienced by others, we model the problem as a noncooperative game. Assuming that each agent controls only a negligible portion of the overall traffic, Nash equilibria in this noncooperative game correspond to s–t flows in which all flow paths have equal latency. A natural measure for the performance of a network used by selfish agents is the common latency experienced by users in a Nash equilibrium. Braess''s Paradox is the counterintuitive but well-known fact that removing edges from a network can improve its performance. Braess''s Paradox motivates the following network design problem: given a network, which edges should be removed to obtain the best flow at Nash equilibrium? Equivalently, given a network of edges that can be built, which subnetwork will exhibit the best performance when used selfishly? We give optimal inapproximability results and approximation algorithms for this network design problem. For example, we prove that there is no approximation algorithm for this problem with approximation ratio less than , where n is the number of network vertices, unless . We further show that this hardness result is the best possible, by exhibiting an -approximation algorithm. We also prove tight inapproximability results when additional structure, such as linearity, is imposed on the network latency functions. Moreover, we prove that an optimal approximation algorithm for these problems is the trivial algorithm: given a network of candidate edges, build the entire network. As a consequence, we show that Braess''s Paradox—even in its worst-possible manifestations—is impossible to detect efficiently. En route to these results, we give a fundamental generalization of Braess''s Paradox: the improvement in performance that can be effected by removing edges can be arbitrarily large in large networks. Even though Braess''s Paradox has enjoyed 35 years as a textbook example, our result is the first to extend its severity beyond that in Braess''s original four-node network. [Copyright &y& Elsevier]

Abstract: We present provably efficient parallel algorithms for sweep scheduling, which is a commonly used technique in radiation transport problems, and involves inverting an operator by iteratively sweeping across a mesh from multiple directions. Each sweep involves solving the operator locally at each cell. However, each direction induces a partial order in which this computation can proceed. On a distributed computing system, the goal is to schedule the computation, so that the length of the schedule is minimized. Due to efficiency and coupling considerations, we have an additional constraint, namely, a mesh cell must be processed on the same processor along each direction. Problems similar in nature to sweep scheduling arise in several other applications, and here we formulate a combinatorial generalization of this problem that captures the sweep scheduling constraints,and call it the generalized sweep scheduling problem. Several heuristics have been proposed for this problem; see [S. Pautz, An algorithm for parallel sweeps on unstructured meshes, Nucl. Sci. Eng. 140 (2002) 111–136; S. Plimpton, B. Hendrickson, S. Burns, W. McLendon, Parallel algorithms for radiation transport on unstructured grids, Super Comput. (2001)] and the references therein; but none of these have provable worst case performance guarantees. Here we present a simple, almost linear time randomized algorithm for the generalized sweep scheduling problem that (provably) gives a schedule of length at most times the optimal schedule for instances with n cells, when the communication cost is not considered, and a slight variant, which coupled with a much more careful analysis, gives a schedule of (expected) length times the optimal schedule for m processors. These are the first such provable guarantees for this problem. The algorithm can be extended with an additional multiplicative factor in the case when we have inter-processor communication latency, in the models of Rayward-Smith [UET scheduling with inter-processor communication delays, Discrete Appl. Math. 18 (1) (1987) 55–71] and Hwang et al. [Scheduling precedence graphs in systems with inter-processor communication times, SIAM J. Comput. 18(2) (1989) 244–257]. Our algorithms are extremely simple, and use no geometric information about the mesh; therefore, these techniques are likely to be applicable in more general settings. We also design a priority based list schedule using these ideas, with the same theoretical guarantee, but much better performance in practice; combining this algorithm with a simple block decomposition also lowers the overall communication cost significantly. Finally, we perform a detailed experimental analysis of our algorithm. Our results indicate that the algorithm compares favorably with the length of the schedule produced by other natural and efficient parallel algorithms proposed in the literature [S. Pautz, An Algorithm for parallel sweeps on unstructured meshes, Nucl. Sci. Eng. 140 (2002) 111–136; S. Plimpton, B. Hendrickson, S. Burns, W. McLendon, Parallel algorithms for radiation transport on unstructured grids, Super Comput. (2001)]. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the problem of determining confluent flows with minimum congestion. A flow of a given commodity is said to be confluent if at any node all the flow of the commodity departs along a single edge. Confluent flows appear in a variety of application areas ranging from wireless communications to evacuations; in fact, most flows in the Internet are confluent since Internet routing is destination based. We consider the single-commodity confluent flow problem, in which we are given an -node directed network , a sink and supplies at each node, and the goal is to find a confluent flow that routes all the supplies to the sink while minimizing the maximum edge congestion. Our main result is an approximation algorithm, based on randomized rounding, for the special case when all the supplies are uniform; the algorithm finds a confluent flow with edge (and node) congestion , where C is the node congestion of a splittable flow with minimum node congestion; here the node congestion of a flow is the maximum, over all nodes other than , of the congestion at a node. This implies an approximation algorithm for the problem with uniform supplies. Our result relies on the analysis of a natural probabilistic process defined on directed acyclic graphs, that may be of independent interest. For tree networks, we present an optimal polynomial-time algorithm for a multi-sink generalization of the above confluent flow problem. We show that it is NP-hard to approximate the congestion of the optimal confluent flow for general networks to within a factor of . We also establish a lower bound on the gap between confluent and splittable flows, and consider multi-commodity and fractional versions of confluent flow problems. [Copyright &y& Elsevier]

Abstract: In a scheduling problem with controllable processing times the job processing time can be compressed through incurring an additional cost. We consider the problem of scheduling n jobs on a single machine with controllable processing times. Each job has a release date when it becomes available for processing, and, after completing its processing, requires an additional delivery time. Feasible schedules are further restricted by job precedence constraints. We develop a polynomial time approximation scheme whose running time depends only linearly on the input size. This improves and generalizes the previous -approximation algorithm by Zdrzalka. Moreover, this linear complexity bound gives a substantial improvement of the best previously known polynomial bound obtained by Hall and Shmoys for the special case without controllable processing times. [Copyright &y& Elsevier]

Abstract: We consider a variety of vehicle routing problems. The input to a problem consists of a graph and edge lengths , . Customers located at the vertices have to be visited by a set of vehicles. Two important parameters are k the number of vehicles, and λ the longest distance traveled by a vehicle. We consider two types of problems. (1) Given a bound λ on the length of each path, find a minimum sized collection of paths that cover all the vertices of the graph, or all the edges from a given subset of edges of the input graph. We also consider a variation where it is desired to cover N by a minimum number of stars of length bounded by λ. (2) Given a number k find a collection of k paths that cover either the vertex set of the graph or a given subset of edges. The goal here is to minimize λ, the maximum travel distance. For all these problems we provide constant ratio approximation algorithms and prove their NP-hardness. [Copyright &y& Elsevier]

Abstract: We present a new hardness of approximation result for the Shortest Vector Problem in norm (denoted by ). Assuming NP ZPP, we show that for every , there is a constant such that for all integers , the problem has no polynomial time approximation algorithm with approximation ratio . [Copyright &y& Elsevier]

Abstract: We study the capacitated vertex cover problem, a generalization of the well-known vertex-cover problem. Given a graph , the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we can cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is clearly NP-hard as it generalizes the well-known vertex-cover problem. Previously, approximation algorithms with an approximation factor of 2 were developed with the assumption that an arbitrary number of copies of a vertex may be chosen in the cover. If we are allowed to pick at most a fixed number of copies of each vertex, the approximation algorithm becomes much more complex. Chuzhoy and Naor (FOCS, 2002) have shown that the weighted version of this problem is at least as hard as set cover; in addition, they developed a 3-approximation algorithm for the unweighted version. We give a 2-approximation algorithm for the unweighted version, improving the Chuzhoy–Naor bound of three and matching (up to lower-order terms) the best approximation ratio known for the vertex-cover problem. [Copyright &y& Elsevier]

Abstract: The main result of this paper is an approximation algorithm for the weighted region optimal path problem. In this problem, a point robot moves in a planar space composed of n triangular regions, each of which is associated with a positive unit weight. The objective is to find, for given source and destination points s and t, a path from s to t with the minimum weighted length. Our algorithm, BUSHWHACK, adopts a traditional approach (see [M. Lanthier, A. Maheshwari, J.-R. Sack, Approximating weighted shortest paths on polyhedral surfaces, in: Proceedings of the 13th Annual ACM Symposium on Coputational Geometry, 1997, pp. 274–283; L. Aleksandrov, M. Lanthier, A. Maheshwari, J.-R. Sack, An ɛ-approximation algorithm for weighted shortest paths on polyhedral surfaces, in: Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, in: Lecture Notes in Comput. Sci., vol. 1432, 1998, pp. 11–22; L. Aleksandrov, A. Maheshwari, J.-R. Sack, Approximation algorithms for geometric shortest path problems, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 286–295]) that converts the original continuous geometric search space into a discrete graph by placing representative points on boundary edges. However, by exploiting geometric structures that we call intervals, BUSHWHACK computes an approximate optimal path more efficiently as it accesses only a sparse subgraph of . Combined with the logarithmic discretization scheme introduced by Aleksandrov et al. [Approximation algorithms for geometric shortest path problems, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 286–295], BUSHWHACK can compute an ɛ-approximation in time. By reducing complexity dependency on ɛ, this result improves on all previous results with the same discretization approach. We also provide an improvement over the discretization scheme of [L. Aleksandrov, A. Maheshwari, J.-R. Sack, Approximation algorithms for geometric shortest path problems, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 286–295] so that the size of is no longer dependent on unit weight ratio, the ratio between the maximum and minimum unit weights. This leads to the first ɛ-approximation algorithm whose time complexity does not depend on unit weight ratio. [Copyright &y& Elsevier]

Abstract: Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing . We give a bicriteria-approximation algorithm that, given , finds a solution of cost times optimal, meeting the covering constraints () and multiplicity constraints (), and satisfying , where is the vector of row sums . Here m denotes the number of rows of . This gives an -approximation algorithm for CIP—minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints . The previous best approximation ratio has been since 1982. CIP contains the set cover problem as a special case, so -approximation is the best possible unless . [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of assigning sensors to track targets so as to minimize the expected error in the resulting estimation for target locations. Specifically, we are interested in how disjoint pairs of bearing or range sensors can be best assigned to targets to minimize the expected error in the estimates. We refer to this as the focus of attention (FOA) problem. In its general form, FOA is NP-hard and not well approximable. However, for specific geometries we obtain significant approximation results: a 2-approximation algorithm for stereo cameras on a line, a (1+ ϵ)-approximation algorithm for any constant ϵ when the cameras are equidistant, and a 1.42-approximation algorithm for equally spaced range sensors on a circle. In addition to constrained geometries, we further investigate the problem for general sensor placement. By reposing as a maximization problem—where the goal is to maximize the number of tracks with bounded error—we are able to leverage results from maximum set-packing to render the problem approximable. We demonstrate the utility of these algorithms in simulation for a target tracking task, and for localizing a team of mobile agents in a sensor network. These results provide insights into sensor/target assignment strategies, as well as sensor placement in a distributed network. [Copyright &y& Elsevier]

Abstract: In TSP with neighborhoods (TSPN) we are given a collection of regions in the plane, called neighborhoods, and we seek the shortest tour that visits all neighborhoods. Until now constant-factor approximation algorithms have been known only for cases where the neighborhoods are of approximately the same size. In this paper we present the first polynomial-time constant-factor approximation algorithm for disjoint convex fat neighborhoods of arbitrary size. We also show that in the general case, where the neighborhoods can overlap and are not required to be convex or fat, TSPN is APX-hard and cannot be approximated within a factor of in polynomial time, unless . [Copyright &y& Elsevier]

Abstract: Given a simple connected graph and a set R of pairs of vertices, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph remains simple and has at least two internally disjoint paths between u and v for each pair . The problem is known to be NP-hard, and a -approximation algorithm has been obtained so far. In this paper, we introduce new stronger lower bounds on the optimal value, and propose an time -approximation algorithm to the problem. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the test set problem and its variations that appear in a variety of applications. In general, we are given a universe of objects to be “distinguished” by a family of “tests”, and we want to find the smallest sufficient collection of tests. In the simplest version, a test is a subset of the universe and two objects are distinguished by our collection if one test contains exactly one of them. Variations allow tests to be multi-valued functions or unions of “basic” tests, and different notions of the term distinguished. An important version of this problem that has applications in DNA sequence analysis has the universe consisting of strings over a small alphabet and tests that are detecting presence (or absence) of a substring. For most versions of the problem, including the latter, we establish matching lower and upper bounds on approximation ratio. When tests can be formed as unions of basic tests, we show that the problem is as hard as the graph coloring problem. We conclude by reporting preliminary computational results on the implementations of our algorithmic approaches for the minimum cost probe set problems on a data set used by Borneman et al. [Copyright &y& Elsevier]

Abstract: We consider the task of SNP (Single Nucleotide Polymorphism) genotyping. In many studies, genotyping of a large number of SNPs must be performed. Multiple SNPs can be genotyped together in the same assay (a process called multiplexed genotyping) provided they adhere to some constraints. We address the optimization problem of designing assays that maximize the number of genotyped SNPs, subject to the multiplexing constraints. We focus on the SNP genotyping method based on primer extension and mass-spectrometry (PEA/MS). We translate the optimization problem to a graph coloring problem, and provide essentially optimal heuristics for solving the corresponding coloring problem. In addition, we consider a method that enables a dramatic increase in the multiplexing rate by modifying primer masses. In this case, the multiplexing design problem can be modelled as a matching problem in hypergraphs. We analyze both theoretical and practical aspects of the problem, providing hardness results and practical heuristics. The heuristics are tested using simulation methods, and prove to be close to optimal in practice. [Copyright &y& Elsevier]

Abstract: We consider the data migration problem, which is the problem of finding an efficient schedule to migrate data in a network. The data layout of a large storage server needs to be computed based on the expected data access pattern for load balancing. As the data access pattern changes over time, we need to recompute a new layout and then migrate the data from its current layout to the new layout. Our objective is to minimize the total completion time over all storage devices. We develop a 3-approximation algorithm when each migration job needs the same amount of time and a 9-approximation when the times required for different migration jobs are different. Another interesting objective is to minimize the total completion time over all data migration jobs. We present a 10-approximation algorithm when each migration job has a different processing time. We extend our results to the resource constrained scheduling problem where each job requires at most m resources. We obtain -approximations for both resource and job completion times. [Copyright &y& Elsevier]

Abstract: We study integrated prefetching and caching in single and parallel disk systems. In the first part of the paper we investigate approximation algorithms for the single disk problem. There exist two very popular approximation algorithms called Aggressive and Conservative for minimizing the total elapsed time. We give a refined analysis of the Aggressive algorithm, improving the original analysis by Cao et al. We prove that our new bound is tight. Additionally we present a new family of prefetching and caching strategies and give algorithms that perform better than Aggressive and Conservative. In the second part of the paper we investigate the problem of minimizing stall time in parallel disk systems. We present a polynomial time algorithm for computing a prefetching/caching schedule whose stall time is bounded by that of an optimal solution. The schedule uses at most extra memory locations in cache. This is the first polynomial time algorithm that, using a small amount of extra resources, computes schedules whose stall times are bounded by that of optimal schedules not using extra resources. Our algorithm is based on the linear programming approach of [Journal of the ACM, 47 (2000) 969]. However, in order to achieve minimum stall times, we introduce the new concept of synchronized schedules in which fetches on the disks are performed completely in parallel. [Copyright &y& Elsevier]

Abstract: The server allocation with bounded simultaneous requests problem arises in isolated infostations, where mobile users going through the coverage area require immediate high-bit rate communications such as web surfing, file transferring, voice messaging, email and fax. Given a set of service requests, each characterized by a temporal interval and a category, an integer k, and an integer for each category c, the problem consists in assigning a server to each request in such a way that at most k mutually simultaneous requests are assigned to the same server at the same time, out of which at most are of category c, and the minimum number of servers is used. Since this problem is computationally intractable, a 2-approximation on-line algorithm is exhibited which asymptotically gives a -approximation, where . Generalizations of the problem are considered, where each request r is also characterized by a bandwidth rate , and the sum of the bandwidth rates of the simultaneous requests assigned to the same server at the same time is bounded, and where each request is characterized also by a gender bandwidth. Such generalizations contain bin-packing, multiprocessor task scheduling, and interval graph coloring as special cases, and they admit on-line algorithms providing constant approximations. [Copyright &y& Elsevier]

We study a generalization of covering problems called partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-partial set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-partial set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-partial vertex cover) in polynomial time. Without making any assumption about the number of sets an element is in, for instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better-than-2-approximation algorithms for k-partial vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-partial vertex cover on planar graphs, and for covering k points in Rd by disks. [Copyright &y& Elsevier]

A prevailing feature of mobile telephony systems is that the cell where a mobile user is located may be unknown. Therefore, when the system is to establish a call between users, it may need to search, or page, all the cells that it suspects the users are located in, to find the cells where the users currently reside. The search consumes expensive wireless links and so it is desirable to develop search techniques that page as few cells as possible.We consider cellular systems with c cells and m mobile users roaming among the cells. The location of the users is uncertain as given by m probability distribution vectors. Whenever the system needs to find specific users, it conducts a search operation lasting some number of rounds (the delay constraint). In each round, the system may check an arbitrary subset of cells to see which users are located there. In this setting the problem of finding one user with minimum expected number of cells searched is known to be solved optimally in polynomial time.In this paper we address the problem of finding several users with the same optimization goal. This task is motivated by the problem of establishing a conference call between mobile users. We first show that the problem is NP-hard. Then we prove that a natural heuristic is an e/(e−1)-approximation solution. [Copyright &y& Elsevier]

Motivated by a scheduling problem in multicast environments, we consider the problem of arranging a weighted graph around a circle so as to minimize the total weighted arc length. We describe the first polynomial-time approximation algorithms for this problem, and specifically an O(logn)-approximation algorithm for undirected circular arrangements and an O(√ of n)-approximation algorithm for directed circular arrangements. We will also conduct an experimental evaluation of our algorithms and show that a simple heuristic has the best performance in simulations based on busy Web server logs. [Copyright &y& Elsevier]

A number of recent papers on approximation algorithms have used the square roots of unity, −1 and 1, to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semidefinite programming in order to obtain near optimum solutions to these problems. In this paper, we consider using the cube roots of unity, 1, ei2π/3, and ei4π/3, to represent ternary decision variables for problems in combinatorial optimization. Here the natural relaxation is that of unit vectors in complex space. We use an extension of semidefinite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique introduced by the authors in Goemans and Williamson (J. ACM 42 (1995) 1115–1145) to obtain near-optimum solutions to the problems. In particular, we consider the problem of maximizing the total weight of satisfied equations xu−xv≡c (mod 3) and inequations xu−xv≢c (mod 3), where xu∈{0,1,2} for all u. This problem can be used to model the Max-3-Cut problem and a directed variant we call Max-3-Dicut. For the general problem, we obtain a 0.793733-approximation algorithm. If the instance contains only inequations (as it does for Max-3-Cut), we obtain a performance guarantee of 7/12+3/4π2arccos2(−1/4)−&epsiv;>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3+3/4π2arccos2(−1/4)−&epsiv;>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3 arccos2(−1/4)−&epsiv;>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3+10−8 for the general problem (by Andersson et al. (J. Algorithms 39 (2001) 162–204)). It matches the guarantee of 0.836008 for Max-3-Cut found independently by de Klerk et al. (On approximate graph colouring and Max-k-Cut algorithms based on the &thetav;-function, Manuscript, October 2000). We show that all these algorithms are in fact equivalent in the case of Max-3-Cut, and that our algorithm is the same as that of Andersson et al. in the more general case. [Copyright &y& Elsevier]

Let P be an optimization problem, and let A be an approximation algorithm for P. The domination ratio domr(A,n) is the maximum real q such that the solution x(I) obtained by A for any instance I of P of size n is not worse than at least a fraction q of the feasible solutions of I. We describe a deterministic, polynomial-time algorithm with domination ratio 1−o(1) for the partition problem, and a deterministic, polynomial-time algorithm with domination ratio Ω(1) for the MaxCut problem and for some far-reaching extensions of it, including Max-r-Sat, for each fixed r. The techniques combine combinatorial and probabilistic methods with tools from harmonic analysis. [Copyright &y& Elsevier]

We consider approximations of the form n1−o(1) for the Maximum Clique problem, where n is the number of vertices in the input graph and where the “o(1)” term goes to zero as n increases. We show that sufficiently strong negative results for such problems, which we call strong inapproximability results, have interesting consequences for exact computation. A simple sampling method underlies most of our results. [Copyright &y& Elsevier]

We study the approximability of edge-disjoint paths and related problems. In the edge-disjoint paths (EDP) problem, we are given a network G with source–sink pairs (si,ti), 1&les;i&les;k, and the goal is to find a largest subset of source–sink pairs that can be simultaneously connected in an edge-disjoint manner. We show that in directed networks, for any &epsiv;>0, EDP is NP-hard to approximate within m1/2−&epsiv;. We also design simple approximation algorithms that achieve essentially matching approximation guarantees for some generalizations of EDP. Another related class of routing problems that we study concerns EDP with the additional constraint that the routing paths be of bounded length. We show that, for any &epsiv;>0, bounded length EDP is hard to approximate within m1/2−&epsiv; even in undirected networks, and give an O(√ of m)-approximation algorithm for it. For directed networks, we show that even the single source–sink pair case (i.e. find the maximum number of paths of bounded length between a given source–sink pair) is hard to approximate within m1/2−&epsiv;, for any &epsiv;>0. [Copyright &y& Elsevier]

The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices {si,ti} of G, find a minimum set of edges of G whose removal disconnects each si from the corresponding ti. Multicut is known to be NP-hard and Max SNP-hard even when the input graph is restricted to being a tree. The main result of the paper is a polynomial-time approximation scheme (PTAS) for Multicut in unweighted graphs with bounded degree and bounded tree-width. That is, for any ∊>0, we present a polynomial-time (1+∊)-approximation algorithm. In the particular case when the input is a bounded-degree tree, we have a linear-time implementation of the algorithm. We also provide some hardness results: we prove that Multicut is still NP-hard for binary trees and that it is Max SNP-hard if we drop any of the three conditions (unweighted, bounded-degree, bounded tree-width). Finally we show that some of these results extend to the vertex version of Multicut and to a directed version of Multicut. [Copyright &y& Elsevier]

We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks. A typical worker’s objective is to minimize the amount of work he does (he is “lazy”), or more generally, to schedule as inefficiently (in some sense) as possible. The worker is subject to the constraint that he must be busy when there is work that he can do; we make this notion precise both in the preemptive and nonpreemptive settings. The resulting class of “perverse” scheduling problems, which we denote “Lazy Bureaucrat Problems,” gives rise to a rich set of new questions that explore the distinction between maximization and minimization in computing optimal schedules. [Copyright &y& Elsevier]

A tree of rings is an undirected graph obtained from a tree by replacing each node of the tree with a cycle (called tree-node-cycle) and then contracting the edges of the tree so that two cycles corresponding to the two end-nodes of any edge have precisely one node in common and no three tree-node-cycles share a same node. (A more general definition may allow them to share the same node.) Given a set of paths on a tree of rings, the path coloring problem is to color these paths with the smallest number of colors so that any two paths sharing an edge are assigned different colors. In this paper, we present a 2-approximation algorithm for this problem. [Copyright &y& Elsevier]

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.''s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem. [Copyright &y& Elsevier]

Scheduling jobs with pairwise conflicts is modeled by the graph multicoloring problem. It occurs in two versions: in the preemptive case, each vertex may get any set of colors, while in the non-preemptive case, the set of colors assigned to each vertex has to be contiguous. We study these versions of the multicoloring problem on trees, under the sum-of-completion-times objective. In particular, we give a quadratic algorithm for the non-preemptive case, and a faster algorithm in the case that all job lengths are short, while we present a polynomial-time approximation scheme for the preemptive case. [Copyright &y& Elsevier]

Wavelength rerouting has been suggested as a viable and cost-effective method to improve the blocking performance of wavelength-routed wavelength-division multiplexing (WDM) networks. This method leads to the following combinatorial optimization problem, dubbed Venetian Routing. Given a directed multigraph G along with two vertices s and t and a collection of pairwise arc-disjoint paths, we wish to find an st-path which arc-intersects the smallest possible number of the given paths. In this paper we prove the computational hardness of this problem even in various special cases, and present several approximation algorithms for its solution. In particular we show a non-trivial connection between Venetian Routing and Label Cover. [Copyright &y& Elsevier]

We obtain the following new coloring results:

Let G be an undirected graph with nonnegative edge lengths. Given two vertices as sources and all vertices as destinations, we investigated the problem how to construct a spanning tree of G such that the sum of distances from sources to destinations is minimum. In the paper, we show the NP-hardness of the problem and present a polynomial time approximation scheme. For any &epsiv;>0, the approximation scheme finds a (1+&epsiv;)-approximation solution in O(n⌈1/&epsiv;+1⌉) time. We also generalize the approximation algorithm to the weighted case for distances that form a metric space. [Copyright &y& Elsevier]

Algorithms for finding similar, or highly conserved, regions in a group of sequences are at the core of many molecular biology problems. Assume that we are given n DNA sequences s1, …, sn. The Consensus Patterns problem, which has been widely studied in bioinformatics research, in its simplest form, asks for a region of length L in each si, and a median string s of length L so that the total Hamming distance from s to these regions is minimized. We show that the problem is NP-hard and give a polynomial time approximation scheme (PTAS) for it. We then present an efficient approximation algorithm for the consensus pattern problem under the original relative entropy measure. As an interesting application of our analysis, we further obtain a PTAS for a restricted (but still NP-hard) version of the important consensus alignment problem allowing at most constant number of gaps, each of arbitrary length, in each sequence. [Copyright &y& Elsevier]