In this paper we study the problem of finding placement tours for pick-and-place robots, also known as the printed circuit board assembly problem with m positions on a board, n bins containing In components and n loca...
详细信息
In this paper we study the problem of finding placement tours for pick-and-place robots, also known as the printed circuit board assembly problem with m positions on a board, n bins containing In components and n locations for the bins. In the standard model where the working time of the robot is proportional to the distances travelled, the general problem appears as a combination of the travelling salesman problem and the matching problem, and for m = n we have an Euclidean, bipartite travelling salesman problem. We give a polynomial-time algorithm which achieves an approximation guarantee of 3 + epsilon. An important special instance of the problem is the case of a fixed assignment of bins to bin-locations. This appears as a special case of a bipartite TSP satisfying the quadrangle inequality and given some fixed matching arcs. We obtain a 1.8 factor approximation with the stacker crane algorithm of Frederikson, Hecht and Kim. For the general bipartite case we also show a 2.0 factor approximation algorithm which is based on a new insertion technique for bipartite TSPs with quadrangle inequality. Implementations and experiments on "real-world" as well as random point configurations conclude this paper.
We present an O(root n log n)-approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves d...
详细信息
We present an O(root n log n)-approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G = (V, E) with nonnegative edge lengths d: E --> R->= 0 and a stretch k >= 1, a subgraph H = (V, E-H) is a k-spanner of G if for every edge (s, t) is an element of E, the graph H contains a path from s to t of length at most k . d(s, t). The previous best approximation ratio was (O) over tilde (n(2/3)), due to Dinitz and Krauthgamer (STOC '11). We also improve the approximation ratio for the important special case of directed 3-spanners with unit edge lengths from (O) over tilde(root n) to O(n(1/3) log n). The best previously known algorithms for this problem are due to Berman, Raskhodnikova and Ruan (FSTTCS '10) and Dinitz and Krauthgamer. The approximation ratio of our algorithm almost matches Dinitz and Krauthgamer's lower bound for the integrality gap of a natural linear programming relaxation. Our algorithm directly implies an O(n(1/3) log n)-approximation for the 3-spanner problem on undirected graphs with unit lengths. An easy O(root n)-approximation algorithm for this problem has been the best known for decades. Finally, we consider the Directed Steiner Forest problem: given a directed graph with edge costs and a collection of ordered vertex pairs, find a minimum-cost subgraph that contains a path between every prescribed pair. We obtain an approximation ratio of O(n(2/3+epsilon)) for any constant epsilon > 0, which improves the O(n(epsilon) . min(n(4/5), m(2/3))) ratio due to Feldman, Kortsarz and Nutov (JCSS'12). (C) 2012 Elsevier Inc. All rights reserved.
In the Euclidean traveling salesman problem with discrete neighborhoods, we are given a set of points P in the plane and a set of n connected regions (neighborhoods), each containing at least one point of P. We seek t...
详细信息
In the Euclidean traveling salesman problem with discrete neighborhoods, we are given a set of points P in the plane and a set of n connected regions (neighborhoods), each containing at least one point of P. We seek to find a tour of minimum length which visits at least one point in each region. We give (i) an O(alpha)-approximation algorithm for the case when the regions are disjoint and alpha-fat, with possibly varying size;(ii) an O(alpha(3))-approximation algorithm for intersecting alpha-fat regions with comparable diameters. These results also apply to the case with continuous neighborhoods, where the sought TSP tour can hit each region at any point. We also give (iii) a simple O(log n)- approximation algorithm for continuous non-fat neighborhoods. The most distinguishing features of these algorithms are their simplicity and low running-time complexities.
Modem distributed telecommunication networks have widely extended the possibilities of the telecommunication industry for offering a wide variety of services, directly or indirectly by facilitating them for other serv...
详细信息
Modem distributed telecommunication networks have widely extended the possibilities of the telecommunication industry for offering a wide variety of services, directly or indirectly by facilitating them for other service providers. As new services are often processing based there is a need for a shift of focus in research from traditional transportation of information to processing of information. This paper considers the problem of installing software applications for services at the computing nodes of the distributed network, in order to maximize the service provider's profit when meeting demand. The service provision problem is formulated as an integer linear programming model and is shown to be NP-hard. We exploit similarities to the well-known (multiple) knapsack problem in devising approximation algorithms and analysing their performance from a worst-case point of view. Among others, a fully polynomial-time approximation scheme is presented for the case with one computing node. The other main results of the paper concern the derivation of upper bounds on the optimal solution via LP. (C) 2002 Elsevier Science B.V. All rights reserved.
Given a set P of n points in R-d and an integer k >= 1, let w* denote the minimum value so that P can be covered by k congruent cylinders of radius w*. We describe a randomized algorithm that, given P and an epsilo...
详细信息
Given a set P of n points in R-d and an integer k >= 1, let w* denote the minimum value so that P can be covered by k congruent cylinders of radius w*. We describe a randomized algorithm that, given P and an epsilon>0, computes k cylinders of radius (1+epsilon) w* that cover P. The expected running time of the algorithm is 0 (n log n), with the constant of proportionality depending on k, d, and epsilon. We first show that there exists a small "certificate" Q subset of P, whose size does not depend on n, such that for any k congruent cylinders that cover Q, an expansion of these cylinders by a factor of (1+epsilon) covers P. We then use a well-known scheme based on sampling and iterated re-weighting for computing the cylinders.
We study the problem of routing and scheduling requests of limited durations in an all-optical network. The task is servicing the requests, assigning each of them a starting time and a wavelength, with restrictions on...
详细信息
We study the problem of routing and scheduling requests of limited durations in an all-optical network. The task is servicing the requests, assigning each of them a starting time and a wavelength, with restrictions on the number of available wavelengths. The goal is minimizing the overall time needed to serve all requests. We propose constant approximation algorithms for both ring and chain networks. In doing this, we also propose a polynomial-time approximation scheme for the problem of routing weighted calls on a directed ring with minimum load. (C) 2002 Elsevier Science B.V. All rights reserved.
We study Connected Facility Location problems. We are given a connected graph G = (V, E) with nonnegative edge cost c(e) for each edge e epsilon E, a set of clients D subset of V such that each client j epsilon D has ...
详细信息
We study Connected Facility Location problems. We are given a connected graph G = (V, E) with nonnegative edge cost c(e) for each edge e epsilon E, a set of clients D subset of V such that each client j epsilon D has positive demand d(j) and a set of facilities F subset of V each has nonnegative opening cost f(i) and capacity to serve all client demands. The objective is to open a subset of facilities, say (F) over cap, to assign each client j epsilon D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost Sigma(i epsilon(F) over cap) f(i) + Sigma (j epsilon D) d(j)c(i(j)j) + M Sigma(e epsilon T) c(e) is minimized for a given input parameter M >= 1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in Algorithmica, 40: 245-269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm.
作者:
Tan, XHTokai Univ
Sch High Technol Human Welfare Numazu 4100395 Japan
Given a simple polygon P with n vertices and a starting point s on its boundary, the watchman route problem asks for a shortest route in P through s such that each point in the interior of the polygon can be seen from...
详细信息
Given a simple polygon P with n vertices and a starting point s on its boundary, the watchman route problem asks for a shortest route in P through s such that each point in the interior of the polygon can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most root2 times that of the shortest watchman route. The best known algorithm for computing the shortest watchman route through s takes 0(n 4) time. In addition, it is too complicated to be suitable in practice. Moreover, our approximation scheme can be applied to the zookeeper's problem, which is a variant of the watchman route problem. (C) 2003 Published by Elsevier B.V.
We study the basic problem of preemptive scheduling of a stream of jobs oil a single processor. Consider all on-line stream of jobs, and let the ith job arrive at time r(i) and have processing time p(i). If C(i) is th...
详细信息
We study the basic problem of preemptive scheduling of a stream of jobs oil a single processor. Consider all on-line stream of jobs, and let the ith job arrive at time r(i) and have processing time p(i). If C(i) is the completion time of job i, then the flow time of i is C(i) - r(i) and the stretch of i is the ratio of its flow time to its processing time: that is, C(i)-r(i)/p(i). Flow time measures the time that a job is in the system regardless of the service it requests', the stretch measure relies oil the intuition that a job that requires a long service time must be prepared to wait longer than jobs that require small service times. We present the improved algorithmic results for the average stretch metric in preemptive uniprocessor scheduling. Our first result is an off-line polynomial-time approximation scheme (PTAS) for average stretch scheduling. This improves upon the 2-approximation achieved by the on-line algorithm SRPT that always schedules a job with the shortest remaining processing time. In a recent work, Chekuri and Khanna (Proc. 34th Ann. Symp. Theory Comput., 297-305, 2002) have presented approximation algorithms for weighted flow time. which is a more general metric than average stretch;their result also yields a PTAS for average stretch. Our second set of results considers the impact of incomplete knowledge of job sizes on the performance of on-line scheduling algorithms. We show that a constant-factor competitive ratio for average stretch is achievable even if the processing times (or remaining processing times) of jobs are known only to within a constant factor of accuracy.
Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. It was shown that if the processor can run at arbitrary speeds and uses power sa when running ...
详细信息
Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. It was shown that if the processor can run at arbitrary speeds and uses power sa when running at speed s(alpha) the online heuristic AVR has a competitive ratio (2 alpha)(alpha)/2. In this paper we first study the online heuristics for the discrete model where the processor can only run at d given speeds. We propose a method to transform online heuristic AVR to an online heuristic for the discrete model and prove a competitive ratio 2(alpha-1)(alpha-1)(alpha-1)(delta(alpha)-1)(alpha)/(delta-1)(delta(alpha)-delta)(alpha-1) + 1, where delta is the maximum ratio between adjacent non-zero speed levels. We also prove that the analysis holds for a class of heuristics that satisfy certain natural properties. We further study the throughput maximization problem when there is an upper bound for the maximum speed. We propose a greedy algorithm with running time O(n(2) log n) and prove that the output schedule is a 3-approximation of the throughput and a (alpha-1)(alpha-1)(3(alpha)-1)(alpha)/2 alpha(alpha)(3(alpha-1)-1)(alpha-1) approximation of the energy consumption. (C) 2010 Elsevier B.V. All rights reserved.
暂无评论