A complete weighted graph G = (V, E, w) is called Delta beta-metric, for some beta >= 1/2, if G satisfies the beta-triangle inequality, i.e., w(u, v) 1/2. Moreover, we give 2 beta-approximation algorithms running ...
详细信息
ISBN:
(数字)9783319946672
ISBN:
(纸本)9783319946672;9783319946665
A complete weighted graph G = (V, E, w) is called Delta beta-metric, for some beta >= 1/2, if G satisfies the beta-triangle inequality, i.e., w(u, v) <= beta . (w(u, x) + w(x, v)) for all vertices u, v, x is an element of V. Given a Delta(beta)-metric graph G = (V, E, w), the Single Allocation at most p-Hub Center Routing problem is to find a spanning subgraph H* of G such that (i) any pair of vertices in C* is adjacent in H* where C*. V and vertical bar C*vertical bar = p;(ii) any pair of vertices in V \ C* is not adjacent in H*;(iii) each v is an element of V \ C* is adjacent to exactly one vertex in C*;and (iv) the routing cost r(H*) = Sigma(u,v is an element of V) d(H)* (u, v) is minimized where d(H)* (u, v) = w(u, f* (u))+ w(f* (u), f* (v))+ w(v, f* (v)) and f* (u), f* (v) are the vertices in C* adjacent to u and v in H*, respectively. Note that w(v, f* (v)) = 0 if v is an element of C*. The vertices selected in C* are called hubs and the rest of vertices are called non-hubs. In this paper, we show that the Single Allocation at most p-Hub Center Routing problem is NP-hard in Delta(beta)-metric graphs for any beta > 1/2. Moreover, we give 2 beta-approximation algorithms running in time O(n(2)) for any beta > 1/2 where n is the number of vertices in the input graph.
Software Defined Networks (SDNs) have been a new paradigm to separate the network control plane from the data forwarding plane. Controller placement is one fundamental problem which identifies the number of controller...
详细信息
We consider stochastic settings for clustering, and develop provably-good (approximation) algorithms for a number of these notions. These algorithms allow one to obtain better approximation ratios compared to the usua...
详细信息
This paper studies the stochastic variant of the classical k-TSP problem where rewards at the vertices are independent random variables which are instantiated upon the tour’s visit. The objective is to minimize the e...
详细信息
A mixed shop is to process a mixture of a set of flow-shop jobs and a set of open-shop jobs. Mixed shops are in general much harder than flow-shops and open-shops, and have been studied since the 1980’s. We consider ...
详细信息
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.
暂无评论