In this paper, we give a framework to design exponential-time approximation schemes for basic graph partitioning problems such as k-WAY CUT, MULTIWAY CUT, STEINER k-CUT and MULTICUT, where the goal is to minimize the ...
详细信息
ISBN:
(纸本)9783959773096
In this paper, we give a framework to design exponential-time approximation schemes for basic graph partitioning problems such as k-WAY CUT, MULTIWAY CUT, STEINER k-CUT and MULTICUT, where the goal is to minimize the number of edges going across the parts. Our motivation to focus on approximation schemes for these problems comes from the fact that while it is possible to solve them exactly in 2nn (1) time (note that this is already faster than brute-forcing over all partitions or edge sets), it is not known whether one can do better. Using our framework, we design the first (1 + 0 -approximation algorithms for the above problems that run in time 2f(')' (for f (6) < 1) for all these problems. As part of our framework, we present two compression procedures. The first of these is a "lossless" procedure, which is inspired by the seminal randomized contraction algorithm for Global Min-cut of Karger [SODA '93]. Here, we reduce the graph to an equivalent instance where the total number of edges is linearly bounded in the number of edges in an optimal solution of the original instance. Following this, we show how a careful combination of greedy choices and the best exact algorithm for the respective problems can exploit this structure and lead to our approximation schemes. Our first compression procedure bounds the number of edges linearly in the optimal solution, but this could still leave a dense graph as the solution size could be superlinear in the number of vertices. However, for several problems, it is known that they admit significantly faster algorithms on instances where solution size is linear in the number of vertices, in contrast to general instances. Hence, a natural question arises here. Could one reduce the solution size to linear in the number of vertices, at least in the case where we are willing to settle for a near-optimal solution, so that the aforementioned faster algorithms could be exploited? In the second compression procedure, using cut sparsifiers
This paper focuses on the Sort & Search method to solve a particular class of single criterion optimization problems called multiple constraints problems. This general method enables to derive exponential-time alg...
详细信息
This paper focuses on the Sort & Search method to solve a particular class of single criterion optimization problems called multiple constraints problems. This general method enables to derive exponential-time algorithms for NP-hard optimization problems. In this paper, this method is further extended to the class of multicriteria multiple constraints problems for which the set of Pareto optima is enumerated. Then, the application of this new method on some multicriteria scheduling problems is proposed, leading to new exponential-time algorithms for those problems.
Given a 1.5-dimensional terrain T, also known as an x-monotone polygonal chain, the Terrain Guarding problem seeks a set of points of minimum size on T that guards all of the points on T. Here, we say that a point p g...
详细信息
Given a 1.5-dimensional terrain T, also known as an x-monotone polygonal chain, the Terrain Guarding problem seeks a set of points of minimum size on T that guards all of the points on T. Here, we say that a point p guards a point q if no point of the line segment (pq) over bar is strictly below T. The Terrain Guarding problem has been extensively studied for over 20 years. In 2005 it was already established that this problem admits a constant-factor approximation algorithm (SODA 2005). However, only in 2010 King and Krohn (SODA 2010) finally showed that Terrain Guarding is NP-hard. In spite of the remarkable developments in approximation algorithms for Terrain Guarding, next to nothing is known about its parameterized complexity. In particular, the most intriguing open questions in this direction ask whether, if parameterized by the size k of a solution guard set, it admits a subexponential-time algorithm and whether it is fixed-parameter tractable. In this article, we answer the first question affirmatively by developing an n(O(root k))-time algorithm for both Discrete Terrain Guarding and Continuous Terrain Guarding. We alsomake non-trivial progress with respect to the second question: we show that Discrete Orthogonal Terrain Guarding, a well-studied special case of Terrain Guarding, is fixed-parameter tractable.
Given a set X of species, a phylogenetic tree is an unrooted binary tree whose leaves are bijectively labelled by X. Such trees can be used to show the way species evolve over time. One way of understanding how topolo...
详细信息
Given a set X of species, a phylogenetic tree is an unrooted binary tree whose leaves are bijectively labelled by X. Such trees can be used to show the way species evolve over time. One way of understanding how topologically different two phylogenetic trees are, is to construct a minimum -size agreement forest: a partition of X into the smallest number of blocks, such that the blocks induce homeomorphic, non -overlapping subtrees in both trees. This is called a maximum agreement forest. This comparison yields insight into commonalities and differences in the evolution of X across the two trees. Computing a maximum agreement forest is NP -hard [8]. In this work we study the problem on caterpillars, which are path -like phylogenetic trees. We will demonstrate that, even if we restrict the input to this highly restricted subclass, the problem remains NP -hard and is in fact APX-hard. Furthermore we show that for caterpillars two standard reduction rules well known in the literature yield a tight kernel of size at most 7k, compared to 15k for general trees [11]. Finally we demonstrate that we can determine if two caterpillars have an agreement forest with at most k blocks in O * (2.49 k ) time, compared to O * (3 k ) for general trees [4], where O * (.) suppresses polynomial factors.
暂无评论