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

A parameterized approximation scheme for Min k-Cut

SIAM JOURNAL ON COMPUTING 2024年第6期53卷 FOCS20-205-FOCS20-238页

作者： Lokshtanov, Daniel Saurabh, Saket Surianarayanan, Vaishali Univ Calif Santa Barbara Santa Barbara CA 93106 USA Inst Math Sci TCS Chennai 600113 Tamil Nadu India

In the Min k-Cut problem, the input consists of an edge weighted graph G and an integer k, and the task is to partition the vertex set into k nonempty sets, such that the total weight of the edges with endpoints in different parts is minimized. When k is part of the input, the problem is NP-complete and hard to approximate within any factor less than 2. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta, Lee, and Li [Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, A. Czumaj, ed., SIAM, Philadelphia, 2018, pp. 2821-2837] initiated the study of FPT-approximation for the Min k-Cut problem and gave a 1.9997-approximation algorithm running in time 2(O(k6))n(O(1)). Later, the same set of authors [Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, M. Thorup, ed., 2018, pp. 113-123] designed a (1 + epsilon)-approximation algorithm that runs in time (k/epsilon)(O(k))n(k+O(1)) and a 1.81-approximation algorithm running in time 2(O(k2))n(O(1)). More, recently, Kawarabayashi and Lin [Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms, S. Chawla, ed., SIAM, Philadelphia, 2020, pp. 990-999] gave a (5/3 + epsilon)-approximation for Min k-Cut running in time 2(O(k2log) (k))n(O(1)). In this paper, we give a parameterized approximation algorithm with best possible approximation guarantee and best possible running time dependence on said guarantee (up to the exponential time hypothesis and constants in the exponent). In particular, for every epsilon>0, the algorithm obtains a (1 + epsilon)-approximate solution in time (k/epsilon)(O(k))n(O(1)). The main ingredients of our algorithm are a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time s(O(k))n(O(1)) on unweighted (multi-) graphs. Here, s denotes the number of edges in a minimum k-cut. The

关键词： MIN k-CUT FPT approximation scheme k-cut sparsifiers approximation algorithms parameterized approximation scheme minimum k-way cuts

来源：评论

学校读者我要写书评

暂无评论

Fixed parameter approximation scheme for min-max k-cut

引用

MATHEMATICAL PROGRAMMING 2023年第2期197卷 1093-1144页

作者： Chandrasekaran, Karthekeyan Wang, Weihang Univ Illinois Champaign IL 61820 USA

We consider the graph k-partitioning problem under the min-max objective, termed as Minmax k-cut. The input here is a graph G = (V, E) with non-negative integral edge weights w : E -> Z(+) and an integer k >= 2 and the goal is to partition the vertices into k non-empty parts V-1, ..., V-k so as to minimize max(i=1)(k) w(delta(V-i)). Although minimizing the sum objective Sigma(k)(i=1) w(delta(V-i)), termed as Minsum k-cut, has been studied extensively in the literature, very little is known about minimizing the max objective. We initiate the study of Minmax k-cut by showing that it is NP-hard and W[1]-hard when parameterized by k, and design a parameterized approximation scheme when parameterized by k. The main ingredient of our parameterized approximation scheme is an exact algorithm for Minmaxk-cut that runs in time (lambda k)(O(k2)) n(O(1)) + O(m), where lambda is value of the optimum, n is the number of vertices, and m is the number of edges. Our algorithmic technique builds on the technique of Lokshtanov, Saurabh, and Surianarayanan (FOCS, 2020) who showed a similar result for Minsum k-cut. Our algorithmic techniques are more general and can be used to obtain parameterized approximation schemes for minimizing l(p)-norm measures of k-partitioning for every p >= 1.

关键词： k-cut Min-max objective parameterized approximation scheme

来源：评论

学校读者我要写书评

暂无评论

parameterized and approximation Algorithms for Coverings Points with Segments in the Plane 41

Parameterized and Approximation Algorithms for Coverings Poi...

引用

41st International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Kowalska, Katarzyna Pilipczuk, Michal Univ Warsaw Fac Math Informat & Mech Warsaw Poland Univ Warsaw Inst Informat Warsaw Poland

ISBN: (纸本)9783959773119

We study parameterized and approximation algorithms for a variant of SET COVER, where the universe of elements to be covered consists of points in the plane and the sets with which the points should be covered are segments. We call this problem SEGMENT SET COVER. We also consider a relaxation of the problem called delta-extension, where we need to cover the points by segments that are extended by a tiny fraction, but we compare the solution's quality to the optimum without extension. For the unparameterized variant, we prove that SEGMENT SET COVER does not admit a PTAS unless P=NP, even if we restrict segments to be axis-parallel and allow 1/2-extension. On the other hand, we show that parameterization helps for the tractability of SEGMENT SET COVER: we give an FPT algorithm for unweighted SEGMENT SET COVER parameterized by the solution size k, a parameterized approximation scheme for WEIGHTED SEGMENT SET COVER with k being the parameter, and an FPT algorithm for WEIGHTED SEGMENT SET COVER with 6 -extension parameterized by k and S. In the last two results, relaxing the problem is probably necessary: we prove that WEIGHTED SEGMENT SET COVER without any relaxation is W[1] -hard and, assuming ETH, there does not exist an algorithm running in time f (k) center dot n(o(k/ log k)). This holds even if one restricts attention to axis-parallel segments.

关键词： Geometric Set Cover fixed-parameter tractability weighted parameterized problems parameterized approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Fixed Parameter approximation scheme for Min-Max k-Cut 22nd

Fixed Parameter Approximation Scheme for Min-Max <i>k</i>-Cu...

引用

22nd International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Chandrasekaran, Karthekeyan Wang, Weihang Univ Illinois Urbana IL 61801 USA

ISBN: (纸本)9783030738792;9783030738785

We consider the graph k-partitioning problem under the min-max objective, termed as MINMAX k-CUT. The input here is a graph G = (V, E) with non-negative edge weights w : E -> R+ and an integer k >= 2 and the goal is to partition the vertices into k non-empty parts V-1,...,V-k so as to minimize max(i=1)(k) w(delta(V-i)). Although minimizing the sum objective Sigma(k)(i=1) w(delta(V-i)), termed as MINSUM k-CUT, has been studied extensively in the literature, very little is known about minimizing the max objective. We initiate the study of MINMAX k-CUT by showing that it is NP-hard and W[1]-hard when parameterized by k, and design a parameterized approximation scheme when parameterized by k. The main ingredient of our parameterized approximation scheme is an exact algorithm for MINMAX k-CUT that runs in time (lambda k)(O(k2))n(O(1)), where lambda is the value of the optimum and n is the number of vertices. Our algorithmic technique builds on the technique of Lokshtanov, Saurabh, and Surianarayanan (FOCS, 2020) who showed a similar result for MINSUM k-CUT Our algorithmic techniques are more general and can be used to obtain parameterized approximation schemes for minimizing l(p)-norm measures of k-partitioning for every p >= 1.

关键词： k-cut Min-max objective parameterized approximation scheme

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：