A unique game is a type of constraint satisfaction problem with two variables per constraint. The value of a unique game is the fraction of the constraints satisfied by an optimal solution. Khot (STOC’02) conjectured...
详细信息
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.
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.
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.
It is desirable to allow packets with the same source and destination to take more than one possible path. This facility can be used to ease congestion and overcome node failures. One approach toward deploying multipa...
详细信息
ISBN:
(纸本)9781424410422
It is desirable to allow packets with the same source and destination to take more than one possible path. This facility can be used to ease congestion and overcome node failures. One approach toward deploying multipath routing in the networks is by creating virtual paths, e.g. using MPLS. There are however costs associated with establishing and maintaining such virtual connections. In this paper, we present the formulation and an approximate solution for the problem of modeling, creation and optimization of the multiple paths in the networks. The aim is to minimize the cost of operating the network and maximize the utilization, using multiple paths. The polynomial-time approximation algorithm presented is based on mixed and linear programming formulation. This approximate solution has a constant approximation ratio;more precisely the throughput of the paths output by our algorithm is at least 0.14 of the optimum throughput, without exceeding the cost of the optimal solution.
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.
Let P be a rectilinear simple polygon. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any axis-parallel line segment inside P. We present a 3-approximation algor...
详细信息
ISBN:
(纸本)9781450306829
Let P be a rectilinear simple polygon. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any axis-parallel line segment inside P. We present a 3-approximation algorithm for the problem of finding a partition with minimum stabbing number. It is based on an algorithm that finds an optimal partition for histograms. We also study Steiner triangulations of a simple (non-rectilinear) polygon P. Here the stabbing number is defined as the maximum number of triangles that can be stabbed by any line segment inside P. We give an O(1)-approximation algorithm for the problem of computing a Steiner triangulation with minimum stabbing number.
We study the l(0)-Low Rank approximation Problem, where the goal is, given an m x n matrix A, to output a rank-k matrix A' for which parallel to A' - A parallel to(0) is minimized. Here, for a matrix B, parall...
详细信息
We study the l(0)-Low Rank approximation Problem, where the goal is, given an m x n matrix A, to output a rank-k matrix A' for which parallel to A' - A parallel to(0) is minimized. Here, for a matrix B, parallel to B parallel to(0) denotes the number of its non-zero entries. This NP-hard variant of low rank approximation is natural for problems with no underlying metric, and its goal is to minimize the number of disagreeing data positions. We provide approximation algorithms which significantly improve the running time and approximation factor of previous work. For k > 1, we show how to find, in poly(mn) time for every k, a rank O(k log(n/k)) matrix A' for which parallel to A' - A parallel to(0) <= O(k(2) log(n/k)) OPT. To the best of our knowledge, this is the first algorithm with provable guarantees for the l(0)-Low Rank approximation Problem for k > 1, even for bicriteria algorithms. For the well-studied case when k = 1, we give a (2+epsilon)-approximation in sublinear time, which is impossible for other variants of low rank approximation such as for the Frobenius norm. We strengthen this for the well-studied case of binary matrices to obtain a (1 + O(psi))-approximation in sublinear time, where psi = OPT /parallel to A parallel to(0). For small psi, our approximation factor is 1 + o(1).
A class of network design problems, including the k-path/tree/cycle covering problems and some location-routing problems, can be modeled by downwards monotone functions [5]. We consider a class of network design probl...
详细信息
ISBN:
(纸本)9783642028816
A class of network design problems, including the k-path/tree/cycle covering problems and some location-routing problems, can be modeled by downwards monotone functions [5]. We consider a class of network design problems, called the p-constrained path/tree/cycle covering problems, obtained by introducing an additional constraint to these problems;i.e., we require that the number of connected components in the optimal solution be at most p for some integer p. The p-constrained path/tree/cycle covering problems cannot be modeled by downwards monotone functions. In this paper, we present a different analysis for the performance guarantee of the algorithm in [5]. As a result of the analysis, we are able to tackle p-constrained path/tree/cycle covering problems, and show the performance bounds of 2 and 4 for p-constrained tree/cycle problems and p-constrained path covering problems respectively.
暂无评论