We study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure D. Given a finite set P of size n, our goal is to find a set C of size k such that the sum of errors D(P, C) = Sigma...
详细信息
We study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure D. Given a finite set P of size n, our goal is to find a set C of size k such that the sum of errors D(P, C) = Sigma(p is an element of P) min(c is an element of C) {D(p, c)} is minimized. The main result in this article can be stated as follows: There exists a (1 + epsilon)-approximation algorithm for the k-median problem with respect to D, if the I-median problem can be approximated within a factor of (1 + epsilon) by taking a random sample of constant size and solving the I-median problem on the sample exactly. This algorithm requires time n2(O(mklog(mk/epsilon))), where m is a constant that depends only on epsilon and D. Using this characterization, we obtain the first linear time (1 + epsilon)-approximation algorithms for the k-median problem in an arbitrary metric space with bounded doubling dimension, for the Kullback-Leibler divergence (relative entropy), for the Itakura-Saito divergence, for Mahalanobis distances, and for some special cases of Bregman divergences. Moreover, we obtain previously known results for the Euclidean k-median problem and the Euclidean k-means problem in a simplified manner. Our results are based on a new analysis of an algorithm of Kumar et al. [2004].
We consider an off-line modified delayed-start LPT algorithm that optimally schedules the first longest 7 jobs and the remaining jobs according to the LPT rule on two identical parallel *** show that this algorithm ha...
详细信息
We consider an off-line modified delayed-start LPT algorithm that optimally schedules the first longest 7 jobs and the remaining jobs according to the LPT rule on two identical parallel *** show that this algorithm has a sharper tight worst-case ratio bound 1 + 1/81 than the traditional LPT algorithm for the sum of squares of machine completion times minimization problem.
This paper presents a novel theoretical analysis for Borda's algorithm and local search algorithm for rank aggregation, which is a heated topic in the field of search technology nowadays and is also known as a ...
详细信息
This paper presents a novel theoretical analysis for Borda's algorithm and local search algorithm for rank aggregation, which is a heated topic in the field of search technology nowadays and is also known as a NPhard problem. In contrast to the previous known approximation ratio of Borda's algorithm, which is 5, we show in this paper that Borda's algorithm is at most 5-8/k approximation for rank aggregation, where k is the number of permutations to be aggregated. Local search algorithm is also widely used in this area but to our best knowledge, there is no approximation ratio analysis for such an algorithm. In other words, this paper proposes the first theoretical analysis for local search rank aggregation algorithm and shows that this algorithm is;actually expected-k/2 approximation. At the end of this paper, several simulation results yields that local search algorithm is a good practical way for the approximation of rank aggregation.
Variants of the facility location problem have been studied extensively in the operations research and management science literatures. In this paper, we present a new analysis method of a simple greedy algorithm for t...
详细信息
ISBN:
(纸本)9781424451920;9781424451937
Variants of the facility location problem have been studied extensively in the operations research and management science literatures. In this paper, we present a new analysis method of a simple greedy algorithm for the uncapacitated facility location problem. We achieve an approximation guarantee of 1.5749 better than 1.853, which is the approximation ratio provided by the combinatorial approximation algorithm due to Charikar and Guha.
＜正＞In the paper,we propose a new d-hop Clustering method for a clustering-based multi-hop routing scheme in large-scale wireless sensor network.d-hop clustering means that each cluster contains all nodes that are a...
详细信息
＜正＞In the paper,we propose a new d-hop Clustering method for a clustering-based multi-hop routing scheme in large-scale wireless sensor network.d-hop clustering means that each cluster contains all nodes that are at distance at most d＜hops from the clusterhead,so that the number of clusters can be getting smaller to make it possible to guarantee the combined system performances including end-to-end delay and *** determine the clusterheads,we give the constraint of minimizing the expected average hop distance from a node to its neatest sink in order to minimize the energy consumption for data forwarding in the clustering-based routing *** deal with the high complexity of the problem,we relax it to a special form of Minimum Weighted d-hop Dominating Set Problem（MWdDSP）,Then we present two approximation algorithms and corresponding analyses for *** is a greedy algorithm with approximation ratio O（lnn）, another achieves a constant factor performance ratio.
In order to solve the nonlinear programming problem with inequality constraints, a method for smoothing the square-root exact penalty function is proposed. Error estimations are obtained among the optimal objectiv...
详细信息
In order to solve the nonlinear programming problem with inequality constraints, a method for smoothing the square-root exact penalty function is proposed. Error estimations are obtained among the optimal objective function values of the smoothed penalty problem, of the nonsmooth exact penalty problem and of the original constrained optimization problem. Based on the smoothed penalty function, an efficient algorithm for solving the optimization problem with inequality constraints is presented. Moreover, the convergence of the algorithm is proved.
This paper considers the generation of the origin-destination (OD) matrix, basic data in any vehicle routing or traveling salesman problem. An OD matrix must be generated by calculating the shortest paths between some...
详细信息
This paper considers the generation of the origin-destination (OD) matrix, basic data in any vehicle routing or traveling salesman problem. An OD matrix must be generated by calculating the shortest paths between some nodes. Candidate methods for this are repetitive use of one-to-all shortest path algorithms such as Dijkstra's algorithm, use of all-to-all shortest path algorithms such as the Floyd-Warshall algorithm, and use of specifically designed some-to-some shortest path algorithms. This paper compares the performance of several shortest path algorithms in computing OD matrices on real road networks. Dijkstra's algorithm with approximate bucket data structure performed the best for most of the networks tested. This paper also proposes a grouping-based algorithm for OD matrix generation. Although it is an approximation approach, it has several good characteristics: it can find the exact shortest distances for most OD pairs;it guarantees that all the calculated shortest path distance values have corresponding paths;the deviation of any distance from the corresponding true shortest distance is small;and its computation time is short. (C) 2008 Elsevier Ltd. All rights reserved.
In this paper we introduce a new general approximation method for set covering problems, based on the combination of randomized rounding of the (near-) optimal solution of the linear programming ( LP) relaxation, lead...
详细信息
In this paper we introduce a new general approximation method for set covering problems, based on the combination of randomized rounding of the (near-) optimal solution of the linear programming ( LP) relaxation, leading to a partial integer solution and the application of a well-behaved approximation algorithm to complete this solution. If the value of the solution returned by the latter can be bounded in a suitable way, as is the case for the most relevant generalizations of bin packing, the method leads to improved approximation guarantees, along with a proof of tighter integrality gaps for the LP relaxation. For d-dimensional vector packing, we obtain a polynomial-time randomized algorithm with asymptotic approximation guarantee arbitrarily close to ln d + 1. For d = 2, this value is 1.693...;i.e., we break the natural 2 "barrier" for this case. Moreover, for small values of d this is a notable improvement over the previously known O(ln d) guarantee by Chekuri and Khanna [SIAM J. Comput., 33 ( 2004), pp. 837-851]. For two-dimensional bin packing with and without rotations, we obtain polynomial-time randomized algorithms with asymptotic approximation guarantee 1.525..., improving upon previous algorithms with asymptotic performance guarantees arbitrarily close to 2 by Jansen and van Stee [ On strip packing with rotations, in Proceedings of the 37th Annual ACM Symposium on the Theory of Computing, 2005, pp. 755-761] for the problem with rotations and 1.691... by Caprara [ Math. Oper. Res., 33 ( 2008), pp. 203-215] for the problem without rotations. The previously unknown key property used in our proofs follows from a retrospective analysis of the implications of the landmark bin packing approximation scheme by Fernandez de la Vega and Lueker [Combinatorica, 1 ( 1981), pp. 349-355]. We prove that their approximation scheme is "subset oblivious," which leads to numerous applications.
This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumabl...
详细信息
This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumable scenario in which the processing can be resumed when the machine next becomes available, and the semi-resumable scenario in which some portion of the processing is repeated but the job is otherwise resumable. For the problem with several non-availability intervals on the first machine under the resumable scenario, we present a fast (3/2)-approximation algorithm. For the problem with one non-availability interval under the semi-resumable scenario, a polynomial-time approximation scheme is developed. (C) 2007 Elsevier Ltd. All rights reserved.
For any epsilon > 0 we give a (2 + epsilon)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [10]. As in [1...
详细信息
For any epsilon > 0 we give a (2 + epsilon)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [10]. As in [10] the algorithm extends to a (2 + epsilon)-approximation algorithm for the minimum tour that visits any k vertices, provided the edge costs satisfy the triangle inequality.
暂无评论