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.
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.
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 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 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 and heuristics for several variations of terrain guarding problems, where we need to guard a terrain in its entirety by a minimum number of guards. Terrain guarding has applications...
详细信息
We present approximation algorithms and heuristics for several variations of terrain guarding problems, where we need to guard a terrain in its entirety by a minimum number of guards. Terrain guarding has applications in telecommunications, namely in the setting up of antenna networks for wireless communication. Our approximation algorithms transform the terrain guarding instance into a MINIMUM SET COVER instance, which is then solved by the standard greedy approximation algorithm [J. Comput. System Sci. 9 (1974) 256-278]. The approximation algorithms achieve approximation ratios of 0(logn), where n is the number of vertices in the input terrain. We also briefly discuss some heuristic approaches for solving other variations of terrain guarding problems, for which no approximation algorithms are known. These heuristic approaches do not guarantee non-trivial approximation ratios but may still yield good solutions. (C) 2002 Published by Elsevier Science B.V.
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.
Wireless energy transfer has emerged as a promising technology for wireless sensor networks to power sensors with controllable yet perpetual energy. In this paper, we study sensor energy replenishment by employing a m...
详细信息
Wireless energy transfer has emerged as a promising technology for wireless sensor networks to power sensors with controllable yet perpetual energy. In this paper, we study sensor energy replenishment by employing a mobile charger (charging vehicle) to charge sensors wirelessly in a rechargeable sensor network, so that the sum of charging rewards collected from all charged sensors by the mobile charger per tour is maximized, subject to the energy capacity of the mobile charger, where the amount of reward received from a charged sensor is proportional to the amount of energy charged to the sensor. The energy of the mobile charger will be spent on both its mechanical movement and sensor charging. We first show that this problem is NP-hard. We then propose approximation algorithms with constant approximation ratios under two different settings: one is that a sensor will be charged to its full energy capacity if it is charged;another is that a sensor can be charged multiple times per tour but the total amount of energy charged is no more than its energy demand prior to the tour. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are very promising, and the solutions obtained are fractional of the optimum. To the best of our knowledge, the proposed algorithms are the very first approximation algorithms with guaranteed approximation ratios for the mobile charger scheduling in a rechargeable sensor network under the energy capacity constraint on the mobile charger.
Predicting the secondary structure of a protein using a lattice model is one of the most studied computational problems in bioinformatics. Here the secondary structure or three dimensional structure of a protein is pr...
详细信息
Predicting the secondary structure of a protein using a lattice model is one of the most studied computational problems in bioinformatics. Here the secondary structure or three dimensional structure of a protein is predicted from its amino acid sequence. The secondary structure refers to the local sub-structures of a protein. Simplified energy models have been proposed in the literature on the basis of interaction of amino acid residues in proteins. We focus on a well researched model known as the Hydrophobic-Polar (HP) energy model. In this paper, we propose the hexagonal prism lattice with diagonals that can overcome the problems of other lattice structures, e.g., parity problem. We give two approximation algorithms for protein folding on this lattice using HP model. Our first algorithm leads us to a similar structure of helix structure that is commonly found in a protein structure. This motivates us to propose the next algorithm with a better approximation ratio. Finally, we analyze the algorithms on the basis of intensity of the chemical forces along the different types of edges of hexagonal prism lattice with diagonals.
暂无评论