Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCovering Tours and Cycle Covers with Turn Costs: Hardness and Approximation
68
0
0.0
(
0
)
Added by
Dominik Michael Krupke
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We investigate a variety of problems of finding tours and cycle covers with minimum turn cost. Questions of this type have been studied in the past, with complexity and approximation results as well as open problems dating back to work by Arkin et al. in 2001. A wide spectrum of practical applications have renewed the interest in these questions, and spawned variants: for full coverage, every point has to be covered, for subset coverage, specific points have to be covered, and for penalty coverage, points may be left uncovered by incurring an individual penalty. We make a number of contributions. We first show that finding a minimum-turn (full) cycle cover is NP-hard even in 2-dimensional grid graphs, solving the long-standing open Problem 53 in The Open Problems Project edited by Demaine, Mitchell and ORourke. We also prove NP-hardness of finding a subset cycle cover of minimum turn cost in thin grid graphs, for which Arkin et al. gave a polynomial-time algorithm for full coverage; this shows that their boundary techniques cannot be applied to compute exact solutions for subset and penalty variants. On the positive side, we establish the first constant-factor approximation algorithms for all considered subset and penalty problem variants, making use of LP/IP techniques. For full coverage in more general grid graphs (e.g., hexagonal grids), our approximation factors are better than the combinatorial ones of Arkin et al. Our approach can also be extended to other geometric variants, such as scenarios with obstacles and linear combinations of turn and distance costs.
rate research
Read More
We consider variants of the following multi-covering problem with disks. We are given two point sets $Y$ (servers) and $X$ (clients) in the plane, a coverage function $kappa :X rightarrow mathcal{N}$, and a constant $alpha geq 1$. Centered at each server is a single disk whose radius we are free to set. The requirement is that each client $x in X$ be covered by at least $kappa(x)$ of the server disks. The objective function we wish to minimize is the sum of the $alpha$-th powers of the disk radii. We present a polynomial time algorithm for this problem achieving an $O(1)$ approximation.
Consider a graph with a rotation system, namely, for every vertex, a circular ordering of the incident edges. Given such a graph, an angle cover maps every vertex to a pair of consecutive edges in the ordering -- an angle -- such that each edge participates in at least one such pair. We show that any graph of maximum degree 4 admits an angle cover, give a poly-time algorithm for deciding if a graph with no degree-3 vertices has an angle-cover, and prove that, given a graph of maximum degree 5, it is NP-hard to decide whether it admits an angle cover. We also consider extensions of the angle cover problem where every vertex selects a fixed number $a>1$ of angles or where an angle consists of more than two consecutive edges. We show an application of angle covers to the problem of deciding if the 2-blowup of a planar graph has isomorphic thickness 2.
We study several problems on geometric packing and covering with movement. Given a family $mathcal{I}$ of $n$ intervals of $kappa$ distinct lengths, and another interval $B$, can we pack the intervals in $mathcal{I}$ inside $B$ (respectively, cover $B$ by the intervals in $mathcal{I}$) by moving $tau$ intervals and keeping the other $sigma = n - tau$ intervals unmoved? We show that both packing and covering are W[1]-hard with any one of $kappa$, $tau$, and $sigma$ as single parameter, but are FPT with combined parameters $kappa$ and $tau$. We also obtain improved polynomial-time algorithms for packing and covering, including an $O(nlog^2 n)$ time algorithm for covering, when all intervals in $mathcal{I}$ have the same length.
We provide a comprehensive study of a natural geometric optimization problem motivated by questions in the context of satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Costs (MSC), we are given a graph $G$ that is embedded in Euclidean space. The edges of $G$ need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan. We show that MSC is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in $Theta(log chi (G))$, while for 3D the minimum scan time is not upper bounded by $chi (G)$. We use this relationship to prove that the existence of a constant-factor approximation implies $P=NP$, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of $frac{3}{2}$, even for bipartite graphs; conversely, we present a $frac{9}{2}$-approximation algorithm for this scenario. Generally, we give an $O(c)$-approximation for $k$-colored graphs with $kleq chi(G)^c$. For general metric cost functions, we provide approximation algorithms whose performance guarantee depend on the arboricity of the graph.
Bribery in election (or computational social choice in general) is an important problem that has received a considerable amount of attention. In the classic bribery problem, the briber (or attacker) bribes some voters in attempting to make the bribers designated candidate win an election. In this paper, we introduce a novel variant of the bribery problem, Election with Bribed Voter Uncertainty or BVU for short, accommodating the uncertainty that the vote of a bribed voter may or may not be counted. This uncertainty occurs either because a bribed voter may not cast its vote in fear of being caught, or because a bribed voter is indeed caught and therefore its vote is discarded. As a first step towards ultimately understanding and addressing this important problem, we show that it does not admit any multiplicative $O(1)$-approximation algorithm modulo standard complexity assumptions. We further show that there is an approximation algorithm that returns a solution with an additive-$epsilon$ error in FPT time for any fixed $epsilon$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
