Given a network and a set of connection requests on it, we consider the maximum edge-disjoint paths and related generalizations and routing problems that arise in assigning paths for these requests. We present improve...
详细信息
Given a network and a set of connection requests on it, we consider the maximum edge-disjoint paths and related generalizations and routing problems that arise in assigning paths for these requests. We present improved approximation algorithms and/or integrality gaps for all problems considered;the central theme of this work is the underlying multicommodity flow relaxation. Applications of these techniques to approximating families of packing integer programs are also presented.
Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning subgraphs (or d-factors...
详细信息
Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning subgraphs (or d-factors) of minimum weight with connectivity requirements. For the case of k-edge-connectedness, we present approximation algorithms that achieve constant approximation ratios for all . For the case of k-vertex-connectedness, we achieve constant approximation ratios for dae -1. Our algorithms also work for arbitrary degree sequences if the minimum degree is at least (for k-edge-connectivity) or 2k-1 (for k-vertex-connectivity). To complement our approximation algorithms, we prove that the problem with simple connectivity cannot be approximated better than the traveling salesman problem. In particular, the problem is APX-hard.
In this paper, we address the problem of constructing required subgraphs using stock pieces of fixed length (CRS-SPFL, for short), which is a new variant of the minimum-cost edge-weighted subgraph (MCEWS, for short) p...
详细信息
In this paper, we address the problem of constructing required subgraphs using stock pieces of fixed length (CRS-SPFL, for short), which is a new variant of the minimum-cost edge-weighted subgraph (MCEWS, for short) problem. Concretely, for the MCEWS problem Q, it is asked to choose a minimum-cost subset of edges from a given graph G such that these edges can form a required subgraph G'. For the CRS-SPFL problem Q ', these edges in such a required subgraph G ' are further asked to be constructed by plus using some stock pieces of fixed length L. The new objective, however, is to minimize the total cost to construct such a required subgraph G ', where the total cost is sum of the cost to purchase stock pieces of fixed length L and the cost to construct all edges in such a subgraph G '. We obtain the following three main results. (1) Given an alpha-approximation algorithm to solve the MCEWS problem, where alpha >= 1 (for the case alpha=1, the MCEWS problem Q is solved optimally by a polynomial-time exact algorithm), we design a 2 alpha-approximation algorithm and another asymptotic 7 alpha 4-approximation algorithm to solve the CRS-SPFL problem Q ', respectively;(2) When Q is the minimum spanning tree problem, we provide a 32-approximation algorithm and an AFPTAS to solve the problem Q ' of constructing a spanning tree using stock pieces of fixed length L, respectively;(3) When Q is the single-source shortest paths tree problem, we present a 32-approximation algorithm and an AFPTAS to solve the problem Q ' of constructing a single-source shortest paths tree using stock pieces of fixed length L, respectively.
We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. Assuming the existence of an integrality gap verifier with a bounded approximation guarantee for the LP ...
详细信息
We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. Assuming the existence of an integrality gap verifier with a bounded approximation guarantee for the LP relaxation of the non-robust version of the problem, we derive approximation algorithms for the robust version under different types of uncertainty, including polyhedral and ellipsoidal uncertainty.
Given a forest F = (V, E) and a positive integer D, we consider the problem of finding a minimum number of new edges E' such that in the augmented graph H = (V, E boolean OR E') any pair of vertices can be con...
详细信息
Given a forest F = (V, E) and a positive integer D, we consider the problem of finding a minimum number of new edges E' such that in the augmented graph H = (V, E boolean OR E') any pair of vertices can be connected by two vertex-disjoint paths of length <= D. We show that this problem and some of its variants are NP-hard, and we present approximation algorithms with worst-case bounds 6 and 4. These algorithms can be implemented in O(vertical bar V vertical bar log vertical bar V vertical bar a) time. (c) 2008 Elsevier B.V. All rights reserved.
The restless bandit problem is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit (MAB) problem in decision theory. In its ultimate generality, the restless bandit problem is ...
详细信息
The restless bandit problem is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit (MAB) problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate to any nontrivial factor, and little progress has been made on this problem despite its significance in modeling activity allocation under uncertainty. In this article, we consider the FEEDBACK MAB problem, where the reward obtained by playing each of n independent arms varies according to an underlying on/off Markov process whose exact state is only revealed when the arm is played. The goal is to design a policy for playing the arms in order to maximize the infinite horizon time average expected reward. This problem is also an instance of a Partially Observable Markov Decision Process (POMDP), and is widely studied in wireless scheduling and unmanned aerial vehicle (UAV) routing. Unlike the stochastic MAB problem, the FEEDBACK MAB problem does not admit to greedy index-based optimal policies. We develop a novel duality-based algorithmic technique that yields a surprisingly simple and intuitive (2 + epsilon)-approximate greedy policy to this problem. We show that both in terms of approximation factor and computational efficiency, our policy is closely related to the Whittle index, which is widely used for its simplicity and efficiency of computation. Subsequently we define a multi-state generalization, that we term MONOTONE bandits, which remains subclass of the restless bandit problem. We show that our policy remains a 2-approximation in this setting, and further, our technique is robust enough to incorporate various side-constraints such as blocking plays, switching costs, and even models where determining the state of an arm is a separate operation from playing it. Our technique is also of independent interest for other restless bandit problems, and we provide an example in nonpreemptive machine replenishment. I
This article presents a new 2-approximation algorithm for a multiple depot, multiple terminal, Hamiltonian path problem when the costs satisfy the triangle inequality. For the case where all the salesmen start from th...
详细信息
This article presents a new 2-approximation algorithm for a multiple depot, multiple terminal, Hamiltonian path problem when the costs satisfy the triangle inequality. For the case where all the salesmen start from the same depot, we present another algorithm with an approximation ratio of 5/3. These results generalize the approximation algorithms currently available for the single depot, single terminal Hamiltonian path problem.
We consider a general class of multiprocessor shop scheduling problems, preemptive or non-preemptive, with precedence constraints between operations, with job or operation release dates, and with a class of objective ...
详细信息
We consider a general class of multiprocessor shop scheduling problems, preemptive or non-preemptive, with precedence constraints between operations, with job or operation release dates, and with a class of objective functions including weighted sums of job, operations and stage completion times. We present a general approximation method combining a linear programming relaxation in the operation completion times, with any algorithm for the makespan version of these problems without release dates. If the latter produces a schedule with makespan no larger than rho times the 'trivial lower bound' consisting of the largest of all stage average loads (or 'congestion') and job lengths (or 'dilation'), then our method produces a feasible schedule with minsum objective no larger than 2ep times the optimum where 2e approximate to 5.44. This leads, in particular, to a polynomial time algorithm with polylogarithmic performance guarantee for the minsum multiprocessor dag-shop problem J(P)\r(ij), dag(f)\Sigma(S) w(S)C(S) where Sigma(S) w(S)C(S) is a general minsum objective including weighted sum of operation and job completion times, stages makespans and others, whereas the best known earlier performance guarantees were 0(m) (where m is the number of stages) for the special cases J\\ SigmaC(j), F(P)\r(j)\ Sigmaw(j)C(j) and O\\SigmaC(j). We also obtain a O(1) performance guarantee for the acyclic job shop problem J\p(ij) = 1,acyclic-dag(j)\Sigma(S) w(S)C(S) with unit processing times and weighted sum of operation (or job) completion time objective. Our results extend to a broad class of minsum objective functions including some convex objectives related to load balancing. We then present an improved 5.83-approximation algorithm for the open shop problem O\r(j)\ E w(j)C(j) with total weighted job completion time objective. We conclude with a very simple method which yields O(m)-approximation algorithms for various job shop problems (preemptive, non-preemptive, and no-wait) with m
We present approximation algorithms for four variations of the maximum latency problem. We consider symmetric graphs and asymmetric graphs and both with general edge weights or weights satisfying the triangle inequali...
详细信息
We present approximation algorithms for four variations of the maximum latency problem. We consider symmetric graphs and asymmetric graphs and both with general edge weights or weights satisfying the triangle inequality. Moreover, in each variation the starting point of the tour may either be given in the input or be a decision variable. As a tool for our solution,we use a PTAS for the maximum partial cover problem. The input to this problem is an edge weighted complete graph and an integer k, and the goal is to compute a maximum weight set of disjoint simple cycles on exactly k vertices. (C) 2008 Elsevier B.V. All rights reserved.
We study a class of problems with both binary selection decisions and associated continuous choices that result in stochastic rewards and costs. The rewards are received based on the decision maker's selection, an...
详细信息
We study a class of problems with both binary selection decisions and associated continuous choices that result in stochastic rewards and costs. The rewards are received based on the decision maker's selection, and the costs depend both on the decisions and realizations of the stochastic variables. We consider a family of risk-based objective functions that contains the traditional risk-neutral expected-value objective as a special case. A combination of rounding and sample average approximation is used to produce solutions that are guaranteed to be close to the optimal solution with high probability. We also provide an empirical comparison of the performance of the algorithms on a set of randomly generated instances of a supply cham example problem. The computational results illustrate the theoretical claims in the paper that, for this problem, high-quality solutions can be found with small computational effort.
暂无评论