In connectivity augmentation problems we are given a graph G=(V,EG)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mat...
详细信息
In connectivity augmentation problems we are given a graph G=(V,EG)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E_G)$$\end{document} and an edge set E on V, and seek a min-size edge set J subset of E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J \subseteq E$$\end{document} such that G boolean OR J\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G \cup J$$\end{document} has larger connectivity than G. In the 1-Connectivity Augmentation (1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1$$\end{document}-CA) problem G is connected and G boolean OR J\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G \cup J$$\end{document} should be 2-connected. In the Leaf to Leaf1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1$$\end{document}-CA every edge in E connects two leaves in the block-tree of G. For this version we give a simple combinatorial 5/3-approximation algorithm, improving the 1.892 appr
Let B be a point robot in the plane, whose path is constrained to have curvature of at most 1, and let Omega be a set of polygonal obstacles with n vertices. We study the collision-free, optimal path-planning problem ...
详细信息
Let B be a point robot in the plane, whose path is constrained to have curvature of at most 1, and let Omega be a set of polygonal obstacles with n vertices. We study the collision-free, optimal path-planning problem for B. Given a parameter epsilon, we present an O((n(2)/epsilon (4)) log n)-time algorithm for computing a collision-free, curvature-constrained path between two given positions, whose length is at most ( 1+epsilon) times the length of an optimal path, provided it is robust. ( Roughly speaking, a path is robust if it remains collision-free even if certain positions on the path are perturbed). Our algorithm thus runs significantly faster than the previously best known algorithm by Jacobs and Canny whose running time is O((n+L/epsilon (2))(2) + n(2)(n+L/epsilon (2)) log n), where L is the total edge length of the obstacles. More importantly, the running time of our algorithm does not depend on the size of obstacles. The path returned by this algorithm is not necessarily robust. We present an O((n(2.5)/epsilon (4)) log n)-time algorithm that returns a robust path whose length is at most ( 1 +) times the length of an optimal path, provided it is robust. We also give a stronger characterization of curvature-constrained shortest paths, which, apart from being crucial for our algorithm, is interesting in its own right. Roughly speaking, we prove that, except in some special cases, a shortest path touches obstacles at points that have a visible vertex nearby.
In this paper, we give the first constant-factor approximation algorithm for the rooted ORIENTEERING problem, as well as a new problem that we call the DISCOUNTED-REWARD traveling salesman problem (TSP), motivated by ...
详细信息
In this paper, we give the first constant-factor approximation algorithm for the rooted ORIENTEERING problem, as well as a new problem that we call the DISCOUNTED-REWARD traveling salesman problem (TSP), motivated by robot navigation. In both problems, we are given a graph with lengths on edges and rewards on nodes, and a start node s. In the ORIENTEERING problem, the goal is to find a path starting at s that maximizes the reward collected, subject to a hard limit on the total length of the path. In the DISCOUNTED-REWARD TSP, instead of a length limit we are given a discount factor gamma, and the goal is to maximize the total discounted reward collected, where the reward for a node reached at time t is discounted by gamma(t). This problem is motivated by an approximation to a planning problem in the Markov decision process (MDP) framework under the commonly employed infinite horizon discounted reward optimality criterion. The approximation arises from a need to deal with exponentially large state spaces that emerge when trying to model one-time events and nonrepeatable rewards (such as for package deliveries). We also consider tree and multiple-path variants of these problems and provide approximations for those as well. Although the unrooted ORIENTEERING problem, where there is no fixed start node s, has been known to be approximable using algorithms for related problems such as kappa-TSP (in which the amount of reward to be collected is fixed and the total length is approximately minimized), ours is the first to approximate the rooted question, solving an open problem in [E. M. Arkin, J. S. B. Mitchell, and G. Narasimhan, Proceedings of the 14th ACM Symposium on Computational Geometry, 1998, pp. 307-316] and [B. Awerbuch, Y. Azar, A. Blum, and S. Vempala, SIAM J. Comput., 28 ( 1998), pp. 254-262]. We complement our approximation result for Orienteering by showing that the problem is APX- hard.
In this paper, we consider the heterogeneous Chinese postman problem (the HCPP), which generalizes the k-Chinese postman problem. Specifically, given a weighted graph G = (V, E;w;r) with length function w : E -> R+...
详细信息
In this paper, we consider the heterogeneous Chinese postman problem (the HCPP), which generalizes the k-Chinese postman problem. Specifically, given a weighted graph G = (V, E;w;r) with length function w : E -> R+ satisfying the triangle inequality, a fixed depot r is an element of V, and k vehicles having k nonuniform speeds lambda(1), lambda(2), ..., lambda(k), respectively, it is asked to find k tours in G for these k vehicles, each starting at the same depot r, and collectively traversing each edge in E at least once. The objective is to minimize the maximum completion time of vehicles, where the completion time of a vehicle is its total travel length divided by its speed. The main contribution of our paper is to show the following two results. (1) Given any small constant delta > 0, we design a 20.8765(1 + delta)-approximation algorithm to solve the HCPP, where the running time required is bounded by a polynomial in the input size and 1/delta. (2) We present a (1 + Delta - 1/k)-approximation algorithm to solve the HCPP in cubic time, where Delta is the ratio of the largest vehicle speed to the smallest one.
We study the covering-type k-violation linear program where at most k of the constraints can be violated. This problem is formulated as a mixed integer program and known to be strongly NP-hard. In this paper, we prese...
详细信息
We study the covering-type k-violation linear program where at most k of the constraints can be violated. This problem is formulated as a mixed integer program and known to be strongly NP-hard. In this paper, we present a simple (k + 1)approximation algorithm using a natural LP relaxation. We also show that the integrality gap of the LP relaxation is k + 1. This implies we can not get better approximation algorithms when we use the LP-relaxation as a lower bound of the optimal value.
The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [J. algorithms, 10 (1989), pp. 568-576;T. Combin. Theory, Ser...
详细信息
The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [J. algorithms, 10 (1989), pp. 568-576;T. Combin. Theory, Ser. B, 57 (1993), pp. 196-206], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O(Vh)-approximation [J. Chen, S. P. Kanchi, and A. Kanevsky, Inform. Process. Lett., 61 (1997), pp. 317-322] is known even in bounded-degree graphs. In this paper we give a polynomial-time algorithm which, given a bounded degree graph of Euler genus g, computes a drawing in a surface of Euler genus go(1) "logo(1) n. Combined with the upper bound from [J. Chen, S. P. Kanchi, and A. Kanevsky, Inform. Process. Lett., 61 (1997), pp. 317-322], our result also implies a 0(n1/2 ')-approximation for some constant a > 0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a uniform fashion, algorithms with approximation ratios of the form OPTc)(1) "logo(1) n for several related problems on bounded-degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion. Our algorithm and proof of correctness for the crossing number problem are simpler compared to the long and difficult proof in the recent breakthrough by Chuzhoy [Proceedings of the ACM Symposium on Theory of Computing, 2011, pp. 303-312], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of the form poly(OPT, log n). We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the
In the problem of scheduling a single machine to minimize total late work, there are n jobs to be processed, each of which has an integer processing time and an integer due date. The objective is to find a sequence of...
详细信息
In the problem of scheduling a single machine to minimize total late work, there are n jobs to be processed, each of which has an integer processing time and an integer due date. The objective is to find a sequence of jobs which minimizes the total late work, where the late work for a job is the amount of processing of this job that is performed after its due date. Three families of approximation algorithms {E(k)}, {A(epsilon)} and (B(epsilon)} are presented. Contained in the first family is a (1 + 1/k)-approximation algorithm E(k), for any positive integer k less-than-or-equal-to n, which uses truncated enumeration;E(k) requires O(n(k+1)) time and O(n) space. The two other families {A(epsilon)} and B(epsilon)} are fully polynomial approximation schemes which are based on the rounding of state variables in dynamic programming formulations. In the superior scheme, for O < epsilon < 1, B(epsilon is a (1 + epsilon)-approximation algorithm which has a time requirement of O(n2/epsilon) and a space requirement of O(n/epsilon).
In this paper,we consider the k-correlation clustering *** an edge-weighted graph G(V,E)where the edges are labeled either“+”(similar)or“−”(different)with nonnegative weights,we want to partition the nodes into at...
详细信息
In this paper,we consider the k-correlation clustering *** an edge-weighted graph G(V,E)where the edges are labeled either“+”(similar)or“−”(different)with nonnegative weights,we want to partition the nodes into at most k-clusters to maximize agreements—the total weights of“+”edges within clusters and“−”edges between *** problem is *** design an approximation algorithm with the approximation ratio{a,(2-k)a+k-1/k},where a is the weighted proportion of“+”edges in all *** a varies from 0 to 1,the approximation ratio varies from k-1/k to 1 and the minimum value is 1/2.
We consider the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. It consists of designing a schedule for a sports league of n teams such that the total traveling costs o...
详细信息
We consider the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. It consists of designing a schedule for a sports league of n teams such that the total traveling costs of the teams are minimized. The most important variant of the traveling tournament problem imposes restrictions on the number of consecutive home games or away games a team may have. We consider the case where at most two consecutive home games or away games are allowed. We show that the well-known independent lower bound for this case cannot be reached and present two approximation algorithms for the problem. The first algorithm has an approximation ratio of in the case that n/2 is odd, and of in the case that n/2 is even. Furthermore, we show that this algorithm is applicable to real world problems as it yields close to optimal tournaments for many standard benchmark instances. The second algorithm we propose is only suitable for the case that n/2 is even and n a parts per thousand yen 12, and achieves an approximation ratio of 1 + 16/n in this case, which makes it the first -approximation for the problem.
The ring loading problem and its variants have been extensively studied in the last fifteen years, under the assumption that all requests have to be satisfied. However, in many practical cases, one may wish to reject ...
详细信息
The ring loading problem and its variants have been extensively studied in the last fifteen years, under the assumption that all requests have to be satisfied. However, in many practical cases, one may wish to reject some requests, which results in a penalty cost. We introduce the ring loading problem with penalty cost, which generalizes the well-known ring loading problem (Schrijver et al., 1999 [14]). We prove that this problem is NP-hard even if the demand can be split, and design a 1.58-approximation algorithm for the integer demand splittable case and a (1.58 + epsilon)-approximation algorithm for the demand unsplittable case, for any given number epsilon > 0. (C) 2013 Elsevier B.V. All rights reserved.
暂无评论