We consider the following problem: Given a graph with edge lengths satisfying the triangle inequality, partition its node set into p subsets, minimizing the total length of edges whose two ends are in the same subset....
详细信息
We consider the following problem: Given a graph with edge lengths satisfying the triangle inequality, partition its node set into p subsets, minimizing the total length of edges whose two ends are in the same subset. For this problem we present an approximation algorithm which comes to at most twice the optimal value. For clustering into two equal-sized sets, the exact bound on the maximum possible error ratio of our algorithm is between 1.686 and 1.7. (C) 1998 Elsevier Science B.V. All rights reserved.
This paper deals with vector covering problems in d-dimensional space. The input to a vector covering problem consists of a set X of d-dimensional vectors in [0, 1](d). The goal is to partition X into a maximum number...
详细信息
This paper deals with vector covering problems in d-dimensional space. The input to a vector covering problem consists of a set X of d-dimensional vectors in [0, 1](d). The goal is to partition X into a maximum number of parts, subject to the constraint that in every part the sum of all vectors is at least one in every coordinate. This problem is known to be NP-complete, and we are mainly interested in its on-line and off-line approximability. For the on-line version, we construct approximation algorithms with worst case guarantee arbitrarily close to 1/(2d) in d greater than or equal to 2 dimensions. This result contradicts a statement of Csirik and Frenk in [5] where it is claimed that, for d greater than or equal to 2, no on-line algorithm can have a worst case ratio better than zero. Moreover, we prove that, for d greater than or equal to 2, no on-line algorithm can have a worst case ratio better than 2/(2d + 1). For the off-line version, we derive polynomial time approximation algorithms with worst case guarantee Theta(1/log d). For d = 2, we present a very fast and very simple off-line approximation algorithm that has worst case ratio 1/2. Moreover, we show that a method from the area of compact vector summation can be used to construct off-line approximation algorithms with worst case ratio 1/d for every d greater than or equal to 2.
There are a number of VLSI problems that have a common structure. We investigate such a structure that leads to a unified approach for three independent VLSI layout problems: partitioning, placement, and via minimizat...
详细信息
There are a number of VLSI problems that have a common structure. We investigate such a structure that leads to a unified approach for three independent VLSI layout problems: partitioning, placement, and via minimization. Along the line, we first propose a linear-time approximation algorithm on maxcut and two closely related problems. k-coloring and maximal k-color ordering problem. The k-coloring is a generalization of the maxcut and the maximal k-color ordering is a generalization of the k-coloring. For a graph G with e edges and n vertices, our maxcut approximation algorithm runs in O(e + n) sequential time yielding a node-balanced maxcut with size at least (w(E) + w(E)/n)/2, improving the time complexity of O(e log e) known before. Building on the proposed maxcut technique and employing a height-balanced binary decomposition, we devise an O((e + n)log k) time algorithm for the k-coloring problem which always finds a k-partition of vertices such that the number of bad (or "defected") edges does not exceed (w(E)/k)((n - 1)/n)(log k), thus improving both the time complexity O(enk) and the bound e/k known before. The other related problem is the maximal k-color ordering problem that has been an open problem [16]. We show the problem is NP-complete, then present an approximation algorithm building on our k-coloring structure. A performance bound on maximal k-color ordering cost, 2kw(E)/3 is attained in O(ek) time. The solution quality of this algorithm is also tested experimentally and found to be effective.
Given a multigraph G = (V, E), the Edge Coloring Problem (ECP) calls for the minimum number chi of colors needed to color the edges in E so that all edges incident with a common node are assigned different colors. The...
详细信息
Given a multigraph G = (V, E), the Edge Coloring Problem (ECP) calls for the minimum number chi of colors needed to color the edges in E so that all edges incident with a common node are assigned different colors. The best known polynomial time approximation algorithms for ECP belong to a same family, which is likely to contain, for each positive integer k, an algorithm which uses at most [((2k + 1)chi + (2k - 2))/2k] colors. For k less than or equal to 5 the existence of the corresponding algorithm was shown, whereas for larger values of k the question is open. We show that, for any k such that the corresponding algorithm exists, it is possible to improve the algorithm so as to use at most [((2k + 1)chi + (2k - 3))/2k] colors. It is easily shown that the (2k - 3)/2k term cannot be reduced further, unless P = NP. We also discuss how our result can be used to extend the set of cases in which well-known conjectures on ECP are valid. (C) 1998 Elsevier Science B.V. All rights reserved.
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached de...
详细信息
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the number of brushes that can be sold in that city. What is the best route to take to sell the quota while traveling the least distance possible? Notice that unlike the standard traveling salesman problem, not only do we need to figure out the order in which to visit the cities, but we must decide the more fundamental question: which cities do we want to visit? In this paper we give the first approximation algorithm having a polylogarithmic performance guarantee for this problem, as well as for the slightly more general "prize-collecting traveling salesman problem" (PCTSP) of Balas, and a variation we call the "bank robber problem" (also called the "orienteering problem" by Golden, Levi, and Vohra). We do this by providing an O(log(2) k) approximation to the somewhat cleaner k-MST problem which is defined as follows. Given an undirected graph on n nodes with nonnegative edge weights and an integer k n, find the tree of least weight that spans k vertices. (If desired, one may specify in the problem a "root vertex" that must be in the tree as well.) Our result improves on the previous best bound of O(root k) of Ravi et al.
We give a concrete example of a family of natural graph-theoretic problems which behave better and better with respect to approximability but none of which are Likely to admit a polynomial time approximation scheme. M...
详细信息
We give a concrete example of a family of natural graph-theoretic problems which behave better and better with respect to approximability but none of which are Likely to admit a polynomial time approximation scheme. More specifically, the family exhibits problems with arbitrarily small, yet positive (assuming P not equal NP), approximation thresholds. The family of problems we give is the independent set problem on k-iterated total graphs, For All k greater than or equal to 1. (C) 1998 Published by Elsevier Science B.V. All rights reserved.
In this paper, we demonstrate the existence of a polynomial time approximation scheme for makespan minimization in the open shop scheduling problem with an a:arbitrary fixed number m of machines. For the variant of th...
详细信息
In this paper, we demonstrate the existence of a polynomial time approximation scheme for makespan minimization in the open shop scheduling problem with an a:arbitrary fixed number m of machines. For the variant of the problem where the number of machines is part of the input, it is known that the existence of an approximation scheme would imply P = NP. Hence, our result draws a precise separating line between approximable cases (i.e., with m fixed) and non-approximable cases (i.e., with m part of the input) of this shop problem. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
Automatic recognition of parts is an important problem in many industrial applications. One model of the problem is: given a finite set of polygonal parts, use a set of "width" measurements taken by a parall...
详细信息
Automatic recognition of parts is an important problem in many industrial applications. One model of the problem is: given a finite set of polygonal parts, use a set of "width" measurements taken by a parallel-jaw gripper to determine which part is present. We study the problem of computing efficient strategies ("grasp plans"), with the goal to minimize the number of measurements necessary in the worst case. We show that finding a minimum length grasp plan is Np-hard, and give a polynomial time approximation algorithm that is simple and produces a solution that is within a log factor from optimal. (C) 1998 Elsevier Science B.V.
暂无评论