检索结果-内蒙古大学图书馆

New subquadratic approximation algorithms for the girth

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Dahlgaard, Søren Bæk Tejs Knudsen, Mathias Stöckel, Morten University of Copenhagen Denmark

We consider the problem of approximating the girth, g, of an unweighted and undirected graph G "pV, Eq with n nodes and m edges. A seminal result of Itai and Rodeh [SICOMP’78] gave an additive 1-approximation in Opn2q time, and the main open question is thus how well we can do in subquadratic time. In this paper we present two main results. The first is a p1 ` Ε, Op1qq-approximation in truly subquadratic time. Specifically, for any k ě 2 our algorithm returns a cycle of length 2 rg{2s ` 2 Q2pkg´1qU in Õpn2´1{kq time. This generalizes the results of Lingas and Lundell [IPL’09] who showed it for the special case of k "2 and Roditty and Vassilevska Williams [SODA’12] who showed it for k "3. Our second result is to present an Op1q-approximation running in Opn1`Εq time for any Ε ą 0. Prior to this work the fastest constant-factor approximation was the Õpn3{2q time 8{3-approximation of Lingas and Lundell [IPL’09] using the algorithm corresponding to the special case k "2 of our first result. Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

Interpolating between k-median and k-center: approximation algorithms for ordered k-median

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Chakrabarty, Deeparnab Swamy, Chaitanya Dept. of Computer Science Dartmouth College HanoverNH03755-3510 United States Dept. of Combinatorics and Optimization Univ. Waterloo WaterlooONN2L 3G1 Canada

We consider a generalization of k-median and k-center, called the ordered k-median problem. In this problem, we are given a metric space (D, {cij}) with n = |D| points, and a non-increasing weight vector w ∈ Rn+, and the goal is to open k centers and assign each point each point j ∈ D to a center so as to minimize w1 · (largest assignment cost) + w2 · (second-largest assignment cost) +... + wn · (n-th largest assignment cost). We give an (18 + ǫ)-approximation algorithm for this problem. Our algorithms utilize Lagrangian relaxation and the primal-dual schema, combined with an enumeration procedure of Aouad and Segev. For the special case of {0, 1}-weights, which models the problem of minimizing the largest assignment costs that is interesting in and of by itself, we provide a novel reduction to the (standard) k-median problem, showing that LP-relative guarantees for k-median translate to guarantees for the ordered k-median problem;this yields a nice and clean (8.5 + ǫ)-approximation algorithm for {0, 1} weights. Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

A Family of approximation algorithms for the Maximum Duo-Preservation String Mapping Problem

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Dudek, Bartlomiej Gawrychowski, Pawel Ostropolski-Nalewaja, Piotr Institute of Computer Science University of Wroclaw Poland University of Haifa Israel

In the Maximum Duo-Preservation String Mapping problem we are given two strings and wish to map the letters of the former to the letters of the latter so as to maximise the number of duos. A duo is a pair of consecutive letters that is mapped to a pair of consecutive letters in the same order. This is complementary to the well-studied Minimum Common String Partition problem, where the goal is to partition the former string into blocks that can be permuted and concatenated to obtain the latter string. Maximum Duo-Preservation String Mapping is APX-hard. After a series of improvements, Brubach [WABI 2016] showed a polynomial-time 3.25-approximation algorithm. Our main contribution is that for any ∊ > 0 there exists a polynomial-time (2 + ∊)-approximation algorithm. Similarly to a previous solution by Boria et al. [CPM 2016], our algorithm uses the local search technique. However, this is used only after a certain preliminary greedy procedure, which gives us more structure and makes a more general local search possible. We complement this with a specialised version of the algorithm that achieves 2.67-approximation in quadratic time. Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

Parameterized approximation algorithms for some location problems in graphs

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Leitert, Arne Dragan, Feodor F. Department of Computer Science Kent State University KentOH United States

We develop efficient parameterized, with additive error, approximation algorithms for the (Connected) r-Domination problem and the (Connected) p-Center problem for unweighted and undirected graphs. Given a graph G, we show how to construct a (connected) (r + O(μ)- dominating set D with |D| ≤ |D∗| efficiently. Here, D∗ is a minimum (connected) r-dominating set of G and μ is our graph parameter, which is the tree-breadth or the cluster diameter in a layering partition of G. Additionally, we show that a +O(μ)-approximation for the (Connected) p-Center problem on G can be computed in polynomial time. Our interest in these parameters stems from the fact that in many real-world networks, including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others, and in many structured classes of graphs these parameters are small constants. Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

Polylogarithmic approximation algorithms for weighted-F-deletion problems

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Agrawal, Akanksha Lokshtanov, Daniel Misra, Pranabendu Saurabh, Saket Zehavi, Meirav University of Bergen Bergen Norway University of Bergen Bergen Norway Institute of Mathematical Sciences Chennai India University of Bergen Bergen Norway Institute of Mathematical Sciences HBNI Chennai India University of Bergen Bergen Norway

Let F be a family of graphs. A canonical vertex deletion problem corresponding to F is defined as follows: given an n-vertex undirected graph G and a weight function w: V (G) → R, find a minimum weight subset S ⊆ V (G) such that G − S belongs to F. This is known as Weighted F Vertex Deletion problem. In this paper we devise a recursive scheme to obtain O(logO(1) n)-approximation algorithms for such problems, building upon the classic technique of finding balanced separators in a graph. Roughly speaking, our scheme applies to those problems, where an optimum solution S together with a well-structured set X, form a balanced separator of the input graph. In this paper, we obtain the first O(logO(1) n)approximation algorithms for the following vertex deletion problems. • We give an O(log2 n)-factor approximation algorithm for Weighted Chordal Vertex Deletion (WCVD), the vertex deletion problem to the family of chordal graphs. On the way to this algorithm, we also obtain a constant factor approximation algorithm for Multicut on chordal graphs. • We give an O(log3 n)-factor approximation algorithm for Weighted Distance Hereditary Vertex Deletion (WDHVD), also known as Weighted Rankwidth-1 Vertex Deletion (WR-1VD). This is the vertex deletion problem to the family of distance hereditary graphs, or equivalently, the family of graphs of rankwidth 1. Our methods also allow us to obtain in a clean fashion a O(log1.5 n)-approximation algorithm for the Weighted F Vertex Deletion problem when F is a minor closed family excluding at least one planar graph. For the unweighted version of the problem constant factor approximation algorithms are were known [Fomin et al., FOCS 2012], while for the weighted version considered here an O(log n log log n)-approximation algorithm follows from [Bansal et al. SODA 2017]. We believe that our recursive scheme can be applied to obtain O(logO(1) n)-approximation algorithms for many other problems as well. Copyright © 2017, The Authors. All rights

关键词： approximation algorithms

Constant approximation algorithms for guarding simple polygons using vertex guards

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Bhattacharya, Pritam Ghosh, Subir Kumar Pal, Sudebkumar Prasant Department of Computer Science and Engineering Indian Institute of Technology Kharagpur West Bengal721302 India Department of Computer Science Rkm Vivekananda Educational and Research Institute Belur West Bengal711202 India

The art gallery problem enquires about the least number of guards sufficient to ensure that an art gallery, represented by a simple polygon P, is fully guarded. Most standard versions of this problem are known to be NP-hard. In 1987, Ghosh provided a deterministic O(log n)-approximation algorithm for the case of vertex guards and edge guards in simple polygons. In the same paper, Ghosh also conjectured the existence of constant ratio approximation algorithms for these problems. We present here three polynomial-time algorithms with a constant approximation ratio for guarding an n-sided simple polygon P using vertex guards. (i) The first algorithm, that has an approximation ratio of 18, guards all vertices of P in O(n4) time. (ii) The second algorithm, that has the same approximation ratio of 18, guards the entire boundary of P in O(n5) time. (iii) The third algorithm, that has an approximation ratio of 27, guards all interior and boundary points of P in O(n5) time. Further, these algorithms can be modified to obtain similar approximation ratios while using edge guards. The significance of our results lies in the fact that these results settle the conjecture by Ghosh regarding the existence of constant-factor approximation algorithms for this problem, which has been open since 1987 despite several attempts by researchers. Our approximation algorithms exploit several deep visibility structures of simple polygons which are interesting in their own right. Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

Experimental Evaluation of approximation algorithms for Maximum Distance-Bounded Subgraph Problems 8

学校读者我要写书评

暂无评论

Experimental Evaluation of Approximation Algorithms for Maxi...

Joint 8th International Conference on Soft Computing and Intelligent Systems (SCIS) / 17th International Symposium on Advanced Intelligent Systems (ISIS)

作者： Asahiro, Yuichi Kubo, Tomohiro Miyano, Eiji Kyushu Sangyo Univ Dept Informat Sci Fukuoka 8138503 Japan Kyushu Inst Technol Dept Syst Design & Informat Fukuoka 8208502 Japan

ISBN: (纸本)9781509026784

In this paper we consider two distance-based relaxed variants of the maximum clique problem (MAX CLIQUE), named MAX d-CLIQUE and MAX d-CLUB: A d-clique in a graph G is a subset S subset of V (G) of vertices such that for pairs of vertices u, v is an element of S, the distance between u and v is at most d in G. A d-club in a graph G is a subset S' subset of V (G) of vertices that induces a subgraph of G of diameter at most d. MAX d-CLIQUE and MAX d-CLUB ask to find a maximum d-clique and a maximum d-club in a given unweighted graph, respectively. MAX 1-CLIQUE and MAX 1-CLUB cannot be efficiently approximated within a factor of n(1-epsilon) for any epsilon > 0 unless P = NP since they are identical to MAX CLIQUE [1], [2]. Also, it is known [3], [4] that it is NP-hard to approximate MAX d-CLIQUE and MAX d-CLUB to within a factor of n(1/2-epsilon) for any fixed d >= 2 and any epsilon > 0. As for approximability of MAX d-CLIQUE and MAX d-CLUB, [3] proposes a polynomial-time algorithm, called ByFindStar(d), and proves that its approximation ratio is O(n(1/2)) and O(n(2/3)) for any even d >= 2 and for any odd d >= 3, respectively. Very recently, a polynomial-time algorithm, called ByFindStar2(d), achieving an optimal approximation ratio of O(n1/2) for MAX d-CLIQUE and MAX d-CLUB is designed for any odd d >= 3 in [4]. In this paper we implement those approximation algorithms and evaluate their quality empirically for random graphs G(n,p),which have n vertices and each edge appears with probability p. The experimental results show that (i) ByFindStar2(d) of approximation ratio O(n(1/2)) can find larger d-clubs (d-cliques) than ByFindStard of approximation ratio O(n(2/3)) for odd d, (ii) the size of d-clubs (d-cliques) output by ByFindStar(d) is the same as ones by ByFindStar2(d) for even d, and (iii) ByFindStar(d) can find the same size of d-clubs (d-cliques) much faster than ByFindStar2(d).

关键词： approximation algorithms

approximation algorithms for Energy, Reliability, and Makespan Optimization Problems

学校读者我要写书评

暂无评论

PARALLEL PROCESSING LETTERS 2016年第1期26卷 1650001-1650001页

作者： Aupy, Guillaume Benoit, Anne Ecole Normale Super Lyon LIP 46 Allee Italie F-69364 Lyon 07 France

We consider the problem of scheduling an application on a parallel computational platform. The application is a particular task graph, either a linear chain of tasks, or a set of independent tasks. The platform is made of identical processors, whose speed can be dynamically modified. It is also subject to failures: if a processor is slowed down to decrease the energy consumption, it has a higher chance to fail. Therefore, the scheduling problem requires us to re-execute or replicate tasks (i.e., execute twice the same task, either on the same processor, or on two distinct processors), in order to increase the reliability. It is a tri-criteria problem: the goal is to minimize the energy consumption, while enforcing a bound on the total execution time (the makespan), and a constraint on the reliability of each task. Our main contribution is to propose approximation algorithms for linear chains of tasks and independent tasks. For linear chains, we design a fully polynomial-time approximation scheme. However, we show that there exists no constant factor approximation algorithm for independent tasks, unless P=NP, and we propose in this case an approximation algorithm with a relaxation on the makespan constraint.

关键词： Scheduling energy reliability makespan models approximation algorithms

Improved approximation algorithms for Hitting 3-Vertex Paths 18th

学校读者我要写书评

暂无评论

Improved Approximation Algorithms for Hitting 3-Vertex Paths

18th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Fiorini, Samuel Joret, Gwenael Schaudt, Oliver Univ Libre Bruxelles Dept Math Brussels Belgium Univ Libre Bruxelles Dept Informat Brussels Belgium Univ Cologne Inst Informat Cologne Germany

ISBN: (纸本)9783319334615;9783319334608

We study the problem of deleting a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. This problem is often called cluster vertex deletion in the literature and admits a straightforward 3-approximation algorithm since it is a special case of the vertex cover problem on a 3-uniform hypergraph. Very recently, You et al. [14] described an efficient 5/2-approximation algorithm for the unweighted version of the problem. Our main result is a 7/3-approximation algorithm for arbitrary weights, using the local ratio technique. We further conjecture that the problem admits a 2-approximation algorithm and give some support for the conjecture. This is in sharp constrast with the fact that the similar problem of deleting vertices to eliminate all triangles in a graph is known to be UGC-hard to approximate to within a ratio better than 3, as proved by Guruswami and Lee [7].

关键词： approximation algorithms