Moss and Rabani study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an O(log n)-approximation algorithm fo...
详细信息
Moss and Rabani study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an O(log n)-approximation algorithm for the node-weighted prize-collecting Steiner tree problem (PCST)-where the goal is to minimize the cost of a tree plus the penalty of vertices not covered by the tree. They use the algorithm for PCST to obtain a bicriteria (2,O(log n))-approximation algorithm for the budgeted node-weighted Steiner tree problem-where the goal is to maximize the prize of a tree with a given budget for its cost. Their solution may cost up to twice the budget, but collects a factor Omega(1/logn) of the optimal prize. We improve these results from at least two aspects. Our first main result is a primal-dual O(log h)-approximation algorithm for a more general problem, node-weighted prize-collecting Steiner forest (PCSF), where we have h demands each requesting the connectivity of a pair of vertices. Our algorithm can be seen as a greedy algorithm which reduces the number of demands by choosing a structure with minimum cost-to-reduction ratio. This natural style of argument leads to a much simpler algorithm than that of Moss and Rabani for PCST. Our second main contribution is for the budgeted node-weighted Steiner tree problem, which is also an improvement to the work of Moss and Rabani. In the unrooted case, we improve upon an existing O(log(2) n)-approximation by Guha et al., and present an O(log n)-approximation algorithm without any budget violation. For the rooted case, where a specified vertex has to appear in the solution tree, we improve the bicriteria result of Moss and Rabani to the bicriteria approximation ratio of (1 + epsilon;O(log n)/epsilon(2)) for any positive (possibly subconstant) epsilon. That is, for any permissible budget violation 1 + epsilon, we present an algorithm achieving a trade off in the guarantee for the prize. Indeed, we show that this is almos
This paper addresses the problem of trajectory planning of a mobile robot for pasture maintenance comprising mulching weeds, reseeding patches without vegetation and spreading cowpats. Based on the sensor-based acquir...
详细信息
This paper addresses the problem of trajectory planning of a mobile robot for pasture maintenance comprising mulching weeds, reseeding patches without vegetation and spreading cowpats. Based on the sensor-based acquired data (points of interest), the proposed approach is to first use an approximation algorithm for data clustering in the form of non-convex and convex hulls. These hulls are then delimited by stair-shaped limits with respect to the working width of the robot, and their centres of gravity calculated. To minimise the travelled distance between the centres of gravity of the defined areas, the Travelling Salesman Problem is addressed via an evolutionary algorithm. Finally, kinematic and dynamic properties of the robot are considered in order to generate the final trajectory. The capabilities of the proposed approaches are highlighted through the processing of several datasets. (C) 2018 IAgrE. Published by Elsevier Ltd. All rights reserved.
Concave mixed- integer quadratic programming is the problem of minimizing a concave quadratic polynomial over the mixed- integer points in a polyhedral region. In this work we describe an algorithm that finds an - app...
详细信息
Concave mixed- integer quadratic programming is the problem of minimizing a concave quadratic polynomial over the mixed- integer points in a polyhedral region. In this work we describe an algorithm that finds an - approximate solution to a concave mixed- integer quadratic programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in 1/ , provided that the number of integer variables and the number of negative eigenvalues of the objective function are fixed. The running time of the proposed algorithm is expected unless P = NP.
We investigate two NP-complete vertex partition problems on edge-weighted complete graphs with 3k vertices. The first problem asks to partition the graph into k vertex disjoint paths of length 2 (referred to as 2-path...
详细信息
We investigate two NP-complete vertex partition problems on edge-weighted complete graphs with 3k vertices. The first problem asks to partition the graph into k vertex disjoint paths of length 2 (referred to as 2-paths) such that the total weight of the paths is maximized. We present a cubic time approximation algorithm that computes a 2-path partition whose total weight is at least .5833 of the weight of an optimal partition, improving upon the (.5265 - is an element of)-approximation algorithm of Tanahashi and Chen (2010). Restricting the input to graphs with edge weights in {0, 1), we present a .75 approximation algorithm improving upon the .55-approximation algorithm of Hassin and Schneider (2013). Combining this algorithm with a previously known approximation algorithm for the 3-SET PACKING problem, we obtain a .6-approximation algorithm for the problem of partitioning a {0, 1)-edge-weighted graph into k vertex disjoint triangles of maximum total weight. The best known approximation algorithm for general weights is due to Chen and Tanahashi (2009) and achieves an approximation ratio of .5257. (C) 2018 Elsevier B.V. All rights reserved.
We study the polynomial time approximation of the NP-hard MAX k-VERTEX COVER problem in bipartite graphs and propose purely combinatorial approximation algorithms . The main result of the paper is a simple combinatori...
详细信息
We study the polynomial time approximation of the NP-hard MAX k-VERTEX COVER problem in bipartite graphs and propose purely combinatorial approximation algorithms . The main result of the paper is a simple combinatorial algorithm and a computer-assisted analysis of its approximation guarantee giving strong evidence that the worst approximation ratio achieved is bounded below by 0.821. We also study two simpler strategies with provable approximation ratios of 2/3 and 34/47 approximate to 0.72 respectively that already beat the only such known algorithm, namely the greedy approach which guarantees ratio (1-1/e) approximate to 0.632. Our principal motivation is to bring a satisfactory answer in the following question: to what extent combinatorial methods for MAX k-VERTEX COVEr compete with linear programming ones? (C) 2017 Elsevier B.V. All rights reserved.
We consider a variety of NP-Complete network connectivity problems. We introduce a novel dual-based approach to approximating network design problems with cut-based linear programming relaxations. This approach gives ...
详细信息
We consider a variety of NP-Complete network connectivity problems. We introduce a novel dual-based approach to approximating network design problems with cut-based linear programming relaxations. This approach gives a 3/2-approximation to Minimum 2-Edge-Connected Spanning Subgraph that is equivalent to a previously proposed algorithm. One well-studied branch of network design models ad hoc networks where each node can either operate at high or low power. If we allow unidirectional links, we can formalize this into the problem Dual Power Assignment (DPA). Our dual-based approach gives a 3 / 2-approximation to DPA, improving the previous best approximation known of . Another standard network design problem is Minimum Strongly Connected Spanning Subgraph (MSCS). We propose a new problem generalizing MSCS and DPA called Star Strong Connectivity (SSC). Then we show that our dual-based approach achieves a 1.6-approximation ratio on SSC. As a consequence of our dual-based approximations, we prove new upper bounds on the integrality gaps of these problems.
The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may ne...
详细信息
The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of n jobs on m distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into m "subjobs" and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem.
作者：
Ma, WillMIT
Ctr Operat Res Cambridge MA 02139 USA
We study the multi-armed bandit problem with arms which are Markov chains with rewards. In the finite-horizon setting, the celebrated Gittins indices do not apply, and the exact solution is intractable. We provide app...
详细信息
We study the multi-armed bandit problem with arms which are Markov chains with rewards. In the finite-horizon setting, the celebrated Gittins indices do not apply, and the exact solution is intractable. We provide approximation algorithms for the general model of Markov decision processes with nonunit transition times. When preemption is allowed, we provide a (1/2 - epsilon)-approximation, along with an example showing this is tight. When preemption isn't allowed, we provide a 1/12-approximation, which improves to a 4/27-approximation when transition times are unity. Our model captures the Markovian Bandits model of Gupta et al., the Stochastic Knapsack model of Dean et al., and the Budgeted Learning model of Guha and Munagala. Our algorithms improve existing results in all three areas. In our analysis, we encounter and overcome to our knowledge a new obstacle: an algorithm that provably exists via analytical arguments, but cannot be found in polynomial time.
Given a graph with a label set , in which each edge has a label from L, and a source together with a sink , the Minimum Label s-t Cut problem asks to pick a set of labels with minimized cardinality, such that the remo...
详细信息
Given a graph with a label set , in which each edge has a label from L, and a source together with a sink , the Minimum Label s-t Cut problem asks to pick a set of labels with minimized cardinality, such that the removal of all edges with labels in from G disconnects s and t. Let and . The previous best known approximation ratio for this problem in literature is . We present two simple and purely combinatorial approximation algorithms for the problem with ratios and , where is the optimal value of the input instance. The former result gives the first approximation ratio which is sublinear in n for the problem, and in particular applies to the instances with dense graphs (e.g., ). The latter result improves the previous ratio , as we can always assume that is a super-constant.
Given a weighted graph G on n + 1 vertices, a spanning K-tree T-K of G is defined to be a spanning tree T of G together with K distinct edges of G that are not edges of T. The objective of the minimum-cost spanning K-...
详细信息
Given a weighted graph G on n + 1 vertices, a spanning K-tree T-K of G is defined to be a spanning tree T of G together with K distinct edges of G that are not edges of T. The objective of the minimum-cost spanning K-tree problem is to choose a subset of edges to form a spanning K-tree with the minimum weight. In this paper, we consider the constructing spanning K-tree problem that is a generalization of the minimum-cost spanning K-tree problem. We are required to construct a spanning K-tree T-K whose n + K edges are assembled from some stock pieces of bounded length L. Let c(0) be the sale price of each stock piece of length L and k(T-K) the number of minimum stock pieces to construct the n + K edges in T-K. For each edge e in G, let c(e) be the construction cost of that edge e. Our new objective is to minimize the total cost of constructing a spanning K-tree T-K, i.e., min(TK) {Sigma(e is an element of TK) c(e) + k(T-K) . c(0)}. The main results obtained in this paper are as follows. (1) A 2-approximation algorithm to solve the constructing spanning K-tree problem. (2) A 3/2-approximation algorithm to solve the special case for constant construction cost of edges. (3) An APTAS for this special case.
暂无评论