In this article, we consider the problem of computing minimum dominating set for a given set @math of @math points in @math . Here the objective is to find a minimum cardinality subset @math of @math such that the union of the unit radius disks centered at the points in @math covers all the points in @math . We first propose a simple 4-factor and 3-factor approximation algorithms in @math and @math time respectively improving time complexities by a factor of @math and @math respectively over the best known result available in the literature [M. De, G.K. Das, P. Carmi and S.C. Nandy, Approximation algorithms for a variant of discrete piercing set problem for unit disk , Int. J. of Comp. Geom. and Appl., to appear]. Finally, we propose a very important shifting lemma, which is of independent interest and using this lemma we propose a @math -factor approximation algorithm and a PTAS for the minimum dominating set problem.
108-approximation algorithm [C a , 2004 @cite_4 ] 72-approximation algorithm [Narayanappa and Voytechovsky, 2006 @cite_20 ] 38-approximation algorithm in O( @math ) time [, 2007 @cite_18 ] 22-approximation algorithm in O( @math ) time [, 2010 @cite_1 ] 18-approximation algorithm in O( @math ) time [, 2012 @cite_5 ] 15-approximation algorithm in O( @math ) time [Fraser and L ' o pez-Ortiz, 2012 @cite_8 ] @math -approximation algorithm in @math time [, 2013 @cite_26 ]
@cite_18 @cite_26 @cite_4 @cite_8 @cite_1 @cite_5 @cite_20
2573057963 816673839 2009279347 2567804199
This paper shows how to compute O(√log n)-approximations to the S PAR S EST CUT and BALANCED SEPARATOR problems in O(n 2 ) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires O(n 9.5 ) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. We present a deterministic (1+o(1))-approximation O(n1 2+o(1)+D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation O(n1 2D1 4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n1 8, and (ii) the O(є−1logє−1)-approximation factor of Lenzen and Patt-Shamir’s O(n1 2+є+D)-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of Ω(n1 2 logn + D) [Das STOC 2011] modulo some lower-order terms, thus essentially settling the status of this problem which was raised at least a decade ago [Elkin SIGACT News 2004]. It also implies a (2+o(1))-approximation O(n1 2+o(1)+D1+o(1))-time algorithm for approximating a network’s weighted diameter which almost matches the lower bound by [PODC 2012]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic, construction of an (no(1), o(1))-hop set of size O(n1+o(1)). We combine these techniques with many distributed algorithmic techniques, some of which from problems that are not directly related to shortest paths, e.g. ruling sets [ STOC 1987], source detection [Lenzen, Peleg PODC 2013], and partial distance estimation [Lenzen, Patt-Shamir PODC 2015]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation O(no(1))-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation O(no(1)logW)-pass O(n1+o(1)logW)-space streaming algorithm, when edge weights are in 1, 2, …, W . The first result answers an open problem in [Nanongkai, STOC 2014]. The second result partially answers an open problem raised by McGregor in 2006 [ sublinear.info , Problem 14]. We give a 7.18-approximation algorithm for the minimum latency problem that uses only @math calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the @math -minimum spanning tree ( @math -MST) problem which is called as a black box for each value of @math . Their algorithm can achieve an approximation factor of 10.77 while making @math PCST calls, a factor of 8.98 using @math PCST calls, or a factor of @math using @math PCST calls, via the @math -MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here @math denotes the number of nodes in the instance, and @math is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in @math time, the overall running time of our algorithm is @math . We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only @math PCST calls, and derandomize it to obtain a deterministic algorithm with factor @math , using @math PCST calls. The basic idea for our improvement is that we do not treat the @math -MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate @math -MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate @math -MSTs for all values of @math , even though we have them only for some values of @math that we are not able to specify in advance. We also extend our algorithm to a weighted version of the minimum latency problem. An important question in theoretical computer science is to determine the best possible running time for solving a problem at hand. For geometric optimization problems, we often understand their complexity on a rough scale, but not very well on a finer scale. One such example is the two-dimensional knapsack problem for squares. There is a polynomial time (1 + ϵ)-approximation algorithm for it (i.e., a PTAS) but the running time of this algorithm is triple exponential in 1 ϵ, i.e., Ω(n221 ϵ). A double or triple exponential dependence on 1 ϵ is inherent in how this and several other algorithms for other geometric problems work. In this paper, we present an EPTAS for knapsack for squares, i.e., a (1+ϵ)-approximation algorithm with a running time of Oϵ(1)·nO(1). In particular, the exponent of n in the running time does not depend on ϵ at all! Since there can be no FPTAS for the problem (unless P = NP) this is the best kind of approximation scheme we can hope for. To achieve this improvement, we introduce two new key ideas: We present a fast method to guess the Ω(221 ϵ) relatively large squares of a suitable near-optimal packing instead of using brute-force enumeration. Secondly, we introduce an indirect guessing framework to define sizes of cells for the remaining squares. In the previous PTAS each of these steps needs a running time of Ω(n221 ϵ) and we improve both to Oϵ(1) · nO(1). We complete our result by giving an algorithm for two-dimensional knapsack for rectangles under (1 + ϵ)-resource augmentation. In this setting, we also improve the best known running time of Ω(n1 ϵ1 ϵ) to Oϵ(1) · nO(1) and compute even a solution with optimal profit, in contrast to the best previously known polynomial time algorithm for this setting that computes only an approximation. We believe that our new techniques have the potential to be useful for other settings as well.