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

16th Latin American Symposium on Theoretical Informatics (LATIN)

作者： Mandal, Soumen Misra, Pranabendu Rai, Ashutosh Saurabh, Saket IIT Delhi Dept Math New Delhi India Chennai Math Inst Chennai Tamil Nadu India Inst Math Sci Chennai Tamil Nadu India Univ Bergen Bergen Norway

ISBN: (纸本)9783031556005;9783031556012

A vertex cover of a graph is a set of vertices of the graph such that every edge has at least one endpoint in it. In this work, we study WEIGHTED VERTEX COVER with solution size as a parameter. Formally, in the (k, W)-VERTEX COVER problem, given a graph G, an integer k, a positive rational W, and a weight function w : V (G) -> Q(+), the question is whether G has a VERTEX COVER of size at most k of weight at most W, with k being the parameter. An (a, b)-bi-criteria approximation algorithm for (k, W)-VERTEX COVER either produces a vertex cover S such that |S| <= ak and w(S) <= bW, or decides that there is no vertex cover of size at most k of weight at most W. We obtain the following results. - A simple (2, 2)-bi-criteria approximation algorithm for (k, W)-VERTEX COVER in polynomial time by modifying the standard LP-rounding algorithm. - A simple exact parameterized algorithm for (k, W)-VERTEX COVER running in O* (1.4656(k)) time (Here, the O* notation hides factors polynomial in n.). - A(1+epsilon, 2)-approximation algorithm for (k, W)-VERTEX COVER running in O* (1.4656((1- epsilon)k)) time. - A (1.5, 1.5)-approximation algorithm for (k, W)-VERTEX COVER running in O* (1.414(k)) time. - A (2 - delta, 2 - delta)-approximation algorithm for (k, W)-VERTEX COVER running in O* (Sigma(i= delta k(1-2 delta)/1+2 delta) (delta k(1-2 delta)/2 delta) ((delta k+i)(delta k-2i delta/1-2 delta))) time for any delta < 0.5. For example, for (1.75, 1.75) and (1.9, 1.9)-approximation algorithms, we get running times of O* (1.272k) and O* (1.151k) respectively. Our algorithms (expectedly) do not improve upon the running times of the existing algorithms for the unweighted version of Vertex Cover. When compared to algorithms for the weighted version, our algorithms are the first ones to the best of our knowledge which work with arbitrary weights, and they perform well when the solution size is much smaller than the total weight of the desired solution.

关键词： Weighted Vertex Cover parameterized Algorithms approximation Algorithms parameterized approximation

来源：评论

学校读者我要写书评

暂无评论

parameterized approximation algorithms for weighted vertex cover

引用

THEORETICAL COMPUTER SCIENCE 2024年 1021卷

作者： Mandal, Soumen Misra, Pranabendu Rai, Ashutosh Saurabh, Saket IIT Delhi Dept Math New Delhi India Chennai Math Inst Chennai India Inst Math Sci Chennai India Univ Bergen Bergen Norway

A vertex cover of a graph is a set of vertices of the graph such that every edge has at least one endpoint in it. In this work, we study Weighted Vertex Cover with solution size as a parameter. Formally, in the (k, W)-Vertex Cover problem, given a graph G, an integer k, a positive rational W, and a weight function w:V(G)-> Q+, the question is whether G has a vertex cover of size at most k of weight at most W, with k being the parameter. An (a,b)-bi-criteria approximation algorithm for (k,W)-Vertex Cover either produces a vertex cover S such that |S|<= ak and w(S)<= bW, or decides that there is no vertex cover of size at most k of weight at most W. We obtain the following results. center dot A simple (2,2)-bi-criteria approximation algorithm for (k,W)-Vertex Cover in polynomial time by modifying the standard LP-rounding algorithm. center dot A simple exact parameterized algorithm for (k,W)-Vertex Cover running in O*(1.4656(k)) time(1). center dot A (1+epsilon,2)-approximation algorithm for (k,W)-Vertex Cover running in O*(1.4656((1-epsilon)k)) time. center dot A (1.5,1.5)-approximation algorithm for (k,W)-Vertex Cover running in O*(1.414(k)) time. center dot A (2-delta,2-delta)-approximation algorithm for (k,W)-Vertex Cover running in O*(Sigma(delta k(1-2 delta)/2 delta)(i=delta k(1-2 delta)/1+2 delta) (delta k+i delta k-2i delta 1-2 delta)) time for any delta<0.5. For example, for (1.75,1.75) and (1.9,1.9)-approximation algorithms, we get running times of O*(1.272(k)) and O*(1.151(k)) respectively. Our algorithms (expectedly) do not improve upon the running times of the existing algorithms for the unweighted version of Vertex Cover. When compared to algorithms for the weighted version, our algorithms are the first ones to the best of our knowledge which work with arbitrary weights, and they perform well when the solution size is much smaller than the total weight of the desired solution.

关键词： Weighted vertex cover parameterized algorithms approximation algorithms parameterized approximation

来源：评论

学校读者我要写书评

暂无评论

parameterized approximation Schemes for Independent Set of Rectangles and Geometric Knapsack 27

Parameterized Approximation Schemes for Independent Set of R...

引用

27th Annual European Symposium on Algorithms (ESA)

作者： Grandoni, Fabrizio Kratsch, Stefan Wiese, Andreas IDSIA USI SUPSI Manno Switzerland Humboldt Univ Inst Informat Berlin Germany Univ Chile Dept Ind Engn Santiago Chile Univ Chile Ctr Math Modeling Santiago Chile

ISBN: (纸本)9783959771245

The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1 + epsilon)-approximations in f( k, epsilon)n(O(1)) time where k is some parameter of the input. The goal is to overcome lower bounds from either of the areas. We obtain the following results on parameterized approximability: - In the maximum independent set of rectangles problem (MISR) we are given a collection of n axis parallel rectangles in the plane. Our goal is to select a maximum-cardinality subset of pairwise non-overlapping rectangles. This problem is NP-hard and also W[1]-hard [Marx, ESA'05]. The best-known polynomial-time approximation factor is O(log log n) [Chalermsook and Chuzhoy, SODA'09] and it admits a QPTAS [Adamaszek and Wiese, FOCS'13;Chuzhoy and Ene, FOCS'16]. Here we present a parameterized approximation scheme (PAS) for misr, i.e. an algorithm that, for any given constant epsilon > 0 and integer k > 0, in time f( k, epsilon)n(g(epsilon)), either outputs a solution of size at least k/(1 + epsilon), or declares that the optimum solution has size less than k. - In the (2-dimensional) geometric knapsack problem (2DK) we are given an axis-aligned square knapsack and a collection of axis-aligned rectangles in the plane (items). Our goal is to translate a maximum cardinality subset of items into the knapsack so that the selected items do not overlap. In the version of 2DK with rotations (2DKR), we are allowed to rotate items by 90 degrees. Both variants are NP-hard, and the best-known polynomial-time approximation factor is 2+ epsilon [Jansen and Zhang, SODA'04]. These problems admit a QPTAS for polynomially bounded item sizes [Adamaszek and Wiese, SODA'15]. We show that both variants are W[1]-hard. Furthermore, we present a PAS for 2DKR. For all considered problems, getting time f( k, epsilon)(nO(1)), rather than f( k, epsilon)n(g(epsilon)), would give FPT time f'(k)n(O(1)) exact algorithms by setting epsilon = 1/( k + 1), contradic

关键词： parameterized approximation parameterized intractability independent set of rectangles geometric knapsack

来源：评论

学校读者我要写书评

暂无评论

parameterized EXACT AND approximation ALGORITHMS FOR MAXIMUM k-SET COVER AND RELATED SATISFIABILITY PROBLEMS

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2016年第3期50卷 227-240页

作者： Bonnet, Edouard Paschos, Vangelis Th. Sikora, Florian Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary PSL Res Univ Univ Paris Dauphine CNRS LAMSADE Paris France

Given a family of subsets S over a set of elements X and two integers p and k, max k-set cover consists of finding a subfamilyT subset of S of cardinality at most k, covering at least p elements of X. This problem is W[2]-hard when parameterized by k, and FPT when parameterized by p. We investigate the parameterized approximability of the problem with respect to parameters k and p. Then, we show that max sat-k, a satisfiability problem generalizing max k-set cover, is also FPT with respect to parameter p.

关键词： parameterized complexity parameterized approximation max k-set cover

来源：评论

学校读者我要写书评

暂无评论

Lossy Kernelization of Same-Size Clustering

引用

THEORY OF COMPUTING SYSTEMS 2023年第4期67卷 785-824页

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Golovach, Petr A. Purohit, Nidhi Simonov, Kirill Portland State Univ Dept Comp Sci Portland OR USA Univ Bergen Dept Informat Bergen Norway Univ Potsdam Hasso Plattner Inst Potsdam Germany

In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) polynomial kernel for this problem parameterized by the cost of clustering. We complement this result by establishing lower bounds for the problem that eliminate the existence of an (exact) kernel of polynomial size and a PTAS.

关键词： k-median clustering parameterized approximation Kernelization Lossy kernels

来源：评论

学校读者我要写书评

暂无评论

parameterized Inapproximability of Independent Set in H-Free Graphs

引用

ALGORITHMICA 2023年第4期85卷 902-928页

作者： Dvorak, Pavel Feldmann, Andreas Emil Rai, Ashutosh Rzazewski, Pawel Charles Univ Prague Fac Math & Phys Prague Czech Republic Warsaw Univ Technol Fac Math & Informat Sci Warsaw Poland Univ Warsaw Inst Informat Warsaw Poland IIT Delhi Dept Math New Delhi India

We study the INDEPENDENT SET problem in H-free graphs, i.e., graphs excluding some fixed graph H as an induced subgraph. We prove several inapproximability results both for polynomial-time and parameterized algorithms. Halldorsson [SODA 1995] showed that for every delta > 0 the INDEPENDENT SET problem has a polynomial-time (d-1/2 + delta)-approximation algorithm in K-1,K-d-free graphs. We extend this result by showing that K-a,K-b-free graphs admit a polynomial-time O(alpha(G)(1-1/a))-approximation, where alpha (G) is the size of a maximum independent set in G. Furthermore, we complement the result of Halldorsson by showing that for some gamma = Theta (d / log d), there is no polynomial-time gamma-approximation algorithm for these graphs, unless NP = ZPP. Bonnet et al. [Algorithmica 2020] showed that INDEPENDENT SET parameterized by the size k of the independent set is W[1]-hard on graphs which do not contain (1) a cycle of constant length at least 4, (2) the star K-1,K-4, and (3) any tree with two vertices of degree at least 3 at constant distance. We strengthen this result by proving three inapproximability results under different complexity assumptions for almost the same class of graphs (we weaken conditions (1) and (2) that G does not contain a cycle of constant length at least 5 or K-1,K-5). First, under the ETH, there is no f (k) . n(o(k/ log k)) algorithm for any computable function f. Then, under the deterministic Gap-ETH, there is a constant delta > 0 such that no delta-approximation can be computed in f (k) . n(O(1)) time. Also, under the stronger randomized Gap-ETH there is no such approximation algorithm with runtime f (k) . n(o(root k)). Finally, we consider the parameterization by the excluded graph H, and show that under the ETH, INDEPENDENT SET has no n(o(alpha(H))) algorithm in H-free graphs. Also, we prove that there is no d/k(o(1)) -approximation algorithm for K-1,K-d-free graphs with runtime f (d, k) . n(O(1)), under the deterministic Gap-ETH.

关键词： Independent set H-free graphs approximation parameterized approximation

来源：评论

学校读者我要写书评

暂无评论

From symmetry to asymmetry: Generalizing TSP approximations by parametrization

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年第1期136卷 157-170页

作者： Behrendt, Lukas Casel, Katrin Friedrich, Tobias Lagodzinski, J. A. Gregor Loeser, Alexander Wilhelm, Marcus Univ Potsdam Hasso Plattner Inst Potsdam Germany Karlsruhe Inst Technol Karlsruhe Germany

We generalize the tree doubling and Christofides algorithm to parameterized approxima-tions for ATSP (constant factor approximations that invest more runtime with respect to a chosen parameter). The parameters we consider are upper bounded by the number of asymmetric distances, which yields algorithms to efficiently compute good approximations for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, with the size of a vertex cover for the sub-graph induced by the edges with asymmetric distances as parameter. Our generalization of tree doubling gives a parameterized 3-approximation, where the parameter is the min-imum number of asymmetric distances in a minimum spanning arborescence. Further, we combine these with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. Since the parameters we consider are theoretically incomparable, we present experimental results showing that generalized tree doubling frequently outper-forms generalized Christofides with respect to parameter size.(c) 2023 Elsevier Inc. All rights reserved.

关键词： parameterized approximation Stability of approximation

来源：评论

学校读者我要写书评

暂无评论

Separating k-MEDIAN from the Supplier Version 25th

Separating k-MEDIAN from the Supplier Version

引用

25th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Anand, Aditya Lee, Euiwoong Univ Michigan Ann Arbor MI 48109 USA

ISBN: (纸本)9783031598340;9783031598357

Given a metric space (V, d) along with an integer k, the k-Median problem asks to open k centers C subset of V to minimize Sigma(v is an element of V) d(v, C), where d(v, C) := mi(n is an element of C) d(v, c). While the best-known approximation ratio 2.613 holds for the more general supplier version where an additional set F subset of V is given with the restriction C subset of F, the best known hardness for these two versions are 1+1/e approximate to 1.36 and 1+2/e approximate to 1.73 respectively, using the same reduction from Maximum k-Coverage. We prove the following two results separating them. 1. We give a 1.546-parameterized approximation algorithm that runs in time f(k)n(O(1)). Since 1+ 2/e is proved to be the optimal approximation ratio for the supplier version in the parameterized setting, this result separates the original k-Median from the supplier version. 2. We prove a 1.416-hardness for polynomial-time algorithms assuming the Unique Games Conjecture. This is achieved via a new finegrained hardness of Maximum k-Coverage for small set sizes. Our upper bound and lower bound are derived from almost the same expression, with the only difference coming from the well-known separation between the powers of LP and SDP on (hypergraph) vertex cover.

关键词： approximation algorithms Clustering parameterized approximation Optimization Hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

Fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs 8th

Fixed-Parameter Algorithms for Cardinality-Constrained Graph...

引用

8th International Symposium on Combinatorial Optimization (ISCO)

作者： Yamada, Suguru Hanaka, Tesshu Kyushu Univ 744MotookaNishi Ku Fukuoka 8190395 Japan

ISBN: (纸本)9783031609237;9783031609244

For an undirected and edge-weighted graph G = (V, E) and a vertex subset S subset of V, we define a function phi(G)(S) := (1 - alpha) center dot w(S) + alpha center dot w(S, V \ S), where alpha is an element of [0, 1] is a real number, w(S) is the sum of weights of edges having two endpoints in S, and w(S, V \ S) is the sum of weights of edges having one endpoint in S and the other in V \ S. Then, given a graph G = (V, E) and a positive integer k, Max (Min) alpha-Fixed Cardinality Graph Partitioning (Max (Min) alpha-FCGP) is the problem to find a vertex subset S subset of V of size k that maximizes (minimizes) (phi G)(S). In this paper, we first show that Max alpha-FCGP with alpha is an element of [1/3, 1] and Min alpha-FCGP with alpha is an element of [0, 1/3] can be solved in time 2 degrees((kd+k))(e + ed)(k)n(O(1)) where k is the solution size, d is the degeneracy of an input graph, and e is Napier's *** we consider Max (Min) Connected alpha-FCGP, which additionally requires the connectivity of a solution. For Max (Min) Connected alpha-FCGP, we give an (e(Delta - 1))(k-1) n (O(1))-time algorithm on general graphs and a 2(O(root k log2 k))n(O(1))-time randomized algorithm on apex-minor-free graphs. Moreover, for Max alpha-FCGP with alpha is an element of [1/3, 1] and Min alpha-FCGP with alpha is an element of [0, 1/3], we propose an (1 + d)(k) 2(o(kd)+O(k))n(O(1))-time algorithm. Finally, we show that they admit FPT-ASs when edge weights are constant.

关键词： Graph partitioning Fixed-parameter tractability Degeneracy parameterized approximation

来源：评论

学校读者我要写书评

暂无评论

approximation Algorithms for Diversity-Bounded Center Problems 17th

Approximation Algorithms for Diversity-Bounded Center Proble...

引用

17th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Han, Lu Liu, Shuilian Xu, Yicheng Zhang, Yong Beijing Univ Posts & Telecommun Sch Sci Beijing 100876 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China

ISBN: (纸本)9783031203497;9783031203503

This paper considers the diversity-bounded center problems, where we are given a set of points, each of which was colored in one of the omega colors, along with integers k and l(i), u(i) for color i, the goal is to select a k-sized center set so as to minimize the maximum distance of a point to its nearest center, and at the same time, meet the requirements that the amount of selected centers with color i must be within left perpendicularl(i), u(i)right perpendicular for each i. The diversity-bounded clustering with one-side upper bound and lower bound requirement was considered in (Jones et al., 2020) and (Thejaswi et al., 2021), respectively. We combine the difficulties of them and propose the diversity-bounded center problems from both sides, and as the main contribution, we present 3-approximation algorithms for the red-blue as well as the multi-colored version, the complexity of which for the latter problem is parameterized by omega.

关键词： Fair clustering Diversity-bounded center approximation algorithm parameterized approximation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：