Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA PTAS for $k$-hop MST on the Euclidean plane: Improving Dependency on $k$
91
0
0.0
(
0
)
Added by
Jittat Fakcharoenphol
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
For any $epsilon>0$, Laue and Matijevi{c} [CCCG07, IPL08] give a PTAS for finding a $(1+epsilon)$-approximate solution to the $k$-hop MST problem in the Euclidean plane that runs in time $(n/epsilon)^{O(k/epsilon)}$. In this paper, we present an algorithm that runs in time $(n/epsilon)^{O(log k cdot(1/epsilon)^2cdotlog^2(1/epsilon))}$. This gives an improvement on the dependency on $k$ on the exponent, while having a worse dependency on $epsilon$. As in Laue and Matijevi{c}, we follow the framework introduced by Arora for Euclidean TSP. Our key ingredients include exponential distance scaling and compression of dynamic programming state tables.
rate research
Read More
Given a graph $G=(V,E)$ and an integer $k ge 1$, a $k$-hop dominating set $D$ of $G$ is a subset of $V$, such that, for every vertex $v in V$, there exists a node $u in D$ whose hop-distance from $v$ is at most $k$. A $k$-hop dominating set of minimum cardinality is called a minimum $k$-hop dominating set. In this paper, we present linear-time algorithms that find a minimum $k$-hop dominating set in unicyclic and cactus graphs. To achieve this, we show that the $k$-dominating set problem on unicycle graph reduces to the piercing circular arcs problem, and show a linear-time algorithm for piercing sorted circular arcs, which improves the best known $O(nlog n)$-time algorithm.
We study the problem of finding a minimum weight connected subgraph spanning at least $k$ vertices on planar, node-weighted graphs. We give a $(4+eps)$-approximation algorithm for this problem. We achieve this by utilizing the recent LMP primal-dual $3$-approximation for the node-weighted prize-collecting Steiner tree problem by Byrka et al (SWAT16) and adopting an approach by Chudak et al. (Math. Prog. 04) regarding Lagrangian relaxation for the edge-weighted variant. In particular, we improve the procedure of picking additional vertices (tree merging procedure) given by Sadeghian (2013) by taking a constant number of recursive steps and utilizing the limited guessing procedure of Arora and Karakostas (Math. Prog. 06). More generally, our approach readily gives a $( icefrac{4}{3}cdot r+eps)$-approximation on any graph class where the algorithm of Byrka et al. for the prize-collecting version gives an $r$-approximation. We argue that this can be interpreted as a generalization of an analogous result by Konemann et al. (Algorithmica~11) for partial cover problems. Together with a lower bound construction by Mestre (STACS08) for partial cover this implies that our bound is essentially best possible among algorithms that utilize an LMP algorithm for the Lagrangian relaxation as a black box. In addition to that, we argue by a more involved lower bound construction that even using the LMP algorithm by Byrka et al. in a emph{non-black-box} fashion could not beat the factor $ icefrac{4}{3}cdot r$ when the tree merging step relies only on the solutions output by the LMP algorithm.
The Non-Uniform $k$-center (NUkC) problem has recently been formulated by Chakrabarty, Goyal and Krishnaswamy [ICALP, 2016] as a generalization of the classical $k$-center clustering problem. In NUkC, given a set of $n$ points $P$ in a metric space and non-negative numbers $r_1, r_2, ldots , r_k$, the goal is to find the minimum dilation $alpha$ and to choose $k$ balls centered at the points of $P$ with radius $alphacdot r_i$ for $1le ile k$, such that all points of $P$ are contained in the union of the chosen balls. They showed that the problem is NP-hard to approximate within any factor even in tree metrics. On the other hand, they designed a bi-criteria constant approximation algorithm that uses a constant times $k$ balls. Surprisingly, no true approximation is known even in the special case when the $r_i$s belong to a fixed set of size 3. In this paper, we study the NUkC problem under perturbation resilience, which was introduced by Bilu and Linial [Combinatorics, Probability and Computing, 2012]. We show that the problem under 2-perturbation resilience is polynomial time solvable when the $r_i$s belong to a constant sized set. However, we show that perturbation resilience does not help in the general case. In particular, our findings imply that even with perturbation resilience one cannot hope to find any good approximation for the problem.
In this paper, we consider the colorful $k$-center problem, which is a generalization of the well-known $k$-center problem. Here, we are given red and blue points in a metric space, and a coverage requirement for each color. The goal is to find the smallest radius $rho$, such that with $k$ balls of radius $rho$, the desired number of points of each color can be covered. We obtain a constant approximation for this problem in the Euclidean plane. We obtain this result by combining a pseudo-approximation algorithm that works in any metric space, and an approximation algorithm that works for a special class of instances in the plane. The latter algorithm uses a novel connection to a certain matching problem in graphs.
We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map graphs, which builds on the result for planar edge weighted instances of Borradaile et al. The Steiner tree problem on map graphs can be casted as a special case of the planar node-weighted Steiner tree problem, for which only a 2.4-approximation is known. We prove and use a contraction decomposition theorem for planar node weighted instances. This readily reduces the problem of finding a PTAS for planar node-weighted Steiner tree to finding a spanner, i.e., a constant-factor approximation containing a nearly optimum solution. Finally, we pin-point places where known techniques for constructing such spanner fail on node weighted instances and further progress requires new ideas.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
