In this paper, we introduce the study of prize-collecting network design problems having general connectivity requirements. Prior work considered only 0-1 or very limited connectivity requirements. We introduce genera...
详细信息
ISBN:
(纸本)9783540939795
In this paper, we introduce the study of prize-collecting network design problems having general connectivity requirements. Prior work considered only 0-1 or very limited connectivity requirements. We introduce general connectivity requirements in the prize-collecting generalized Steiner tree framework of Hajiaghayi and Jain [9], and consider penalty functions linear in the violation of the connectivity requirements. Using Jain's iterated rounding algorithm [11] as a black box, and ideas from Goemans [7] and Levi, Lodi, Sviridenko [14], we give a 2.54-factor approximation algorithm for the problem. We also generalize the 0-1 requirements of PCF problem introduced by Sharma, Swamy, and Williamson [15] to include general connectivity requirements. Here we assume that the monotone submodular penalty function of Sharma et al. is generalized to a multiset function that can be decomposed into functions in the same form as that of Sharma et al. Using ideas from Goemans and Berstimas [6], we give an (a log K)-approximation algorithm for the resulting problem, where K is the maximum connectivity requirement, and alpha = 2.54.
Karloff and Zwick obtained recently an optimal 7/8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7/8-approximation algorithm for MAX SAT, we consider the m...
详细信息
ISBN:
(数字)9783540487777
ISBN:
(纸本)3540660194
Karloff and Zwick obtained recently an optimal 7/8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7/8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-SAT, namely MAX 4-SAT. We present a semidefinite programming relaxation of MAX 4-SAT and a new family of rounding procedures that try to cope well with clauses of various sizes. We study the potential, and the limitations, of the relaxation and of the proposed family of rounding procedures using a combination of theoretical and experimental means. We select two rounding procedures from the proposed family of rounding procedures. Using the first rounding procedure we seem to obtain an almost optimal 0.8721-approximation algorithm for MAX 4-SAT. Using the second rounding procedure we seem to obtain an optimal 7/8-approximation algorithm for satisfiable instances of MAX 4-SAT. On the other hand, we show that no rounding procedure from the family considered can yield an approximation algorithm for MAX 4-SAT whose performance guarantee on all instances of the problem is greater than 0.8724. Although most of this paper deals specifically with the MAX 4-SAT problem, we believe that the new family of rounding procedures introduced, and the methodology used in the design and in the analysis of the various rounding procedures considered would have a much wider range of applicability.
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 TSP, motivated by robot navigation. In both prob...
详细信息
ISBN:
(纸本)0769520405
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 TSP, motivated by robot navigation. In both problems, we are given a graph with lengths on edges and prizes (rewards) on nodes, and a start node s. In the Orienteering Problem, the goal is to find a path 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 total discounted reward collected, where reward for a node reached at time t is discounted by gamma(t). This is similar to the objective considered in Markov Decision Processes (MDPs) except we only receive a reward the first time a node is visited. 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 k-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 [3, 1].
An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S subset of V that maximizes the number of edges in the cut delta(S) such that t...
详细信息
ISBN:
(纸本)9783662483503;9783662483497
An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S subset of V that maximizes the number of edges in the cut delta(S) such that the induced graph G[S] is connected. We present the first nontrivial Omega(1/log n) approximation algorithm for the connected maximum cut problem in general graphs using novel techniques. We then extend our algorithm to an edge weighted case and obtain a poly- logarithmic approximation algorithm. Interestingly, in stark contrast to the classical max- cut problem, we show that the connected maximum cut problem remains NP- hard even on unweighted, planar graphs. On the positive side, we obtain a polynomial time approximation scheme for the connected maximum cut problem on planar graphs and more generally on graphs with bounded genus.
The rectilinear Steiner tree problem with a family D of obstacles H[D(i)] (1 <= i <= delta = vertical bar D vertical bar) is defined as follows: given a rectangular grid graph H = (N, A), a family D of obstacles...
详细信息
ISBN:
(纸本)0780388348
The rectilinear Steiner tree problem with a family D of obstacles H[D(i)] (1 <= i <= delta = vertical bar D vertical bar) is defined as follows: given a rectangular grid graph H = (N, A), a family D of obstacles, and a set P of terminals not contained in any obstacle, find a rectilinear Steiner tree connecting P in H - boolean OR(Di epsilon D) Di. The case with edge weight being unity is exclusively considered in the paper. First, for the case with D = theta, we propose approximation algorithms by improving those which are already existing. Secondly, we propose other capable approximation algorithms by extending existing ones so that the case with D not equal theta may be handled. Evaluation of their performance through experimental results is given.
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 present approximation algorithms for the unsplittable flow problem (UFP) in undirected graphs. As is standard in this line of research, we assume that the maximum demand is at most the minimum Capacity. We focus on...
详细信息
ISBN:
(数字)9783540457534
ISBN:
(纸本)9783540441861
We present approximation algorithms for the unsplittable flow problem (UFP) in undirected graphs. As is standard in this line of research, we assume that the maximum demand is at most the minimum Capacity. We focus on the non-uniform capacity case in which the edge capacities can vary arbitrarily over the graph. Our results are: We obtain an O(Delta alpha(-1) log(2) n) approximation ratio for UFP, where n is the number of vertices, Delta is the maximum degree, and alpha is the expansion of the graph. Furthermore, if we specialize to the case where all edges have the same capacity, Our algorithm gives an O(Delta alpha(-1) log n) approximation. For certain strong constant-degree expanders considered by Frieze [17] we obtain an O(root log n) approximation for the uniform capacity case. For UFP on the line and the ring, we give the first constant-factor approximation algorithms. All of the above results improve if the maximum demand is bounded away from the minimum capacity. The above results either improve upon or are incomparable with previously known results for these problems. The main technique used for these results is randomized rounding followed by greedy alteration, and is inspired by the use of this idea in recent work.
The traveling purchaser problem is a generalization of the traveling salesman problem with applications in a wide range of areas including network design and scheduling. The input consists of a set of markets and a se...
详细信息
ISBN:
(纸本)3540662510
The traveling purchaser problem is a generalization of the traveling salesman problem with applications in a wide range of areas including network design and scheduling. The input consists of a set of markets and a set of products. Each market offers a price for each product and there is a cost associated with traveling from one market to another. The problem is to purchase all products by visiting a subset of the markets in a tour such that the total travel and purchase costs are minimized. This problem includes many well-known NP-hard problems such as uncapacitated facility location, set cover and group Steiner tree problems as its special cases. We give an approximation algorithm with a poly-logarithmic worst-case ratio for the traveling purchaser problem with metric travel costs. For a special case of the problem that models the ring-star network design problem, we give a constant-factor approximation algorithm. Our algorithms are based on rounding LP relaxation solutions.
In the stochastic knapsack problem, we are given a knapsack of size B, and a set of items whose sizes and rewards are drawn from a known probability distribution. To know the actual size and reward we have to schedule...
详细信息
ISBN:
(纸本)9780769545714
In the stochastic knapsack problem, we are given a knapsack of size B, and a set of items whose sizes and rewards are drawn from a known probability distribution. To know the actual size and reward we have to schedule the item-when it completes, we get to know these values. The goal is to schedule the items (possibly making adaptive decisions based on the sizes seen so far) to maximize the expected total reward of items which successfully pack into the knapsack. We know constant-factor approximations when (i) the rewards and sizes are independent, and (ii) we cannot prematurely cancel items after we schedule them. What if either or both assumptions are relaxed? Related stochastic packing problems are the multi-armed bandit (and budgeted learning) problems;here one is given several arms which evolve in a specified stochastic fashion with each pull, and the goal is to (adaptively) decide which arms to pull, in order to maximize the expected reward obtained after B pulls in total. Much recent work on this problem focuses on the case when the evolution of each arm follows a martingale, i. e., when the expected reward from one pull of an arm is the same as the reward at the current state. What if the rewards do not form a martingale? In this paper, we give O(1)-approximation algorithms for the stochastic knapsack problem with correlations and/or cancellations. Extending the ideas developed here, we give O(1)-approximations for MAB problems without the martingale assumption. Indeed, we can show that previously proposed linear programming relaxations for these problems have large integrality gaps. So we propose new time-indexed LP relaxations;using a decomposition and "gapfilling" approach, we convert these fractional solutions to distributions over strategies, and then use the LP values and the time ordering information from these strategies to devise randomized adaptive scheduling algorithms.
We consider several variants of a car-sharing problem. Given are a number of requests each consisting of a pick-up location and a drop-off location, a number of cars, and nonnegative, symmetric travel times that satis...
详细信息
ISBN:
(纸本)9783030581503;9783030581497
We consider several variants of a car-sharing problem. Given are a number of requests each consisting of a pick-up location and a drop-off location, a number of cars, and nonnegative, symmetric travel times that satisfy the triangle inequality. Each request needs to be served by a car, which means that a car must first visit the pick-up location of the request, and then visit the drop-off location of the request. Each car can serve two requests. One problem is to serve all requests with the minimum total travel time (called CSsum), and the other problem is to serve all requests with the minimum total latency (called CSlat). We also study the special case where the pick-up and drop-off location of a request coincide. We propose two basic algorithms, called the match and assign algorithm and the transportation algorithm. We show that the best of the resulting two solutions is a 2-approximation for CSsum (and a 7/5-approximation for its special case), and a 5/3-approximation for CSlat (and a 3/2-approximation for its special case);these ratios are better than the ratios of the individual algorithms. Finally, we indicate how our algorithms can be applied to more general settings where each car can serve more than two requests, or where cars have distinct speeds.
暂无评论