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

4th International Workshop on parameterized and Exact Computation

作者： Golovach, Petr A. Thilikos, Dimitrios M. Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Univ Athens Dept Math Natl & Kapodistrian GR-15784 Athens Greece

ISBN: (纸本)9783642112683

We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem anti the bounded length cut problem. From Menger's theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target;paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length of paths, the number k of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both A: and I and hardness results when the parameter is only one of A: and I. Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph.

关键词： Bounded length disjoint paths Bounded length cuts parameterized complexity parameterized Algorithms

来源：评论

学校读者我要写书评

暂无评论

Extension of Some Edge Graph Problems: Standard and parameterized complexity 22nd

Extension of Some Edge Graph Problems: Standard and Paramete...

引用

22nd International Symposium on Fundamentals of Computation Theory (FCT)

作者： Casel, Katrin Fernau, Henning Ghadikolaei, Mehdi Khosravian Monnot, Jerome Sikora, Florian Univ Potsdam Hasso Plattner Inst D-14482 Potsdam Germany Univ Trier Fachbereich 4 Informat Wissensch D-54286 Trier Germany Univ Paris 09 PSL Univ LAMSADE CNRS F-75016 Paris France

ISBN: (纸本)9783030250270;9783030250263

We consider extension variants of some edge optimization problems in graphs containing the classical EDGE COVER, MATCHING, and EDGE DOMINATING SET problems. Given a graph G = (V, E) and an edge set U subset of E, it is asked whether there exists an inclusion-wise minimal (resp., maximal) feasible solution E' which satisfies a given property, for instance, being an edge dominating set (resp., a matching) and containing the forced edge set U (resp., avoiding any edges from the forbidden edge set E\U). We present hardness results for these problems, for restricted instances such as bipartite or planar graphs. We counterbalance these negative results with parameterized complexity results. We also consider the price of extension, a natural optimization problem variant of extension problems, leading to some approximation results.

关键词： Extension problems Edge cover Matching Edge domination NP-completeness parameterized complexity Approximation

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Group Activity Selection 17

Parameterized Complexity of Group Activity Selection

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Hooyeon Lee Virginia Vassilevska Williams Moloco Inc. Massachusetts Institute of Technology

ISBN: (纸本)9781510855076

We consider the Group Activity Selection Problem (GASP) in which a group of agents need to be assigned to activities, subject to agent preferences and stability conditions. In GASP, the agents announce dichotomic preferences on which (activity, number-of-participant) pairs are acceptable to them. We consider five solution concepts of assignments: (1) individual rationality (everyone who is assigned to an activity is willing to participate), (2) (Nash) stability (no agent wants to deviate from the assignment), (3) envy-freeness (no agent is envious of someone else's assignment), (4) stability and envy-freeness, and (5) perfection (everyone is assigned and willing to participate). It is known that finding an assignment of a given size with any of these properties is NP-complete. We study the complexity of GASPon a finer scale, through the lens of parameterized complexity. We show that the solution concepts above differ substantially, when parameterized by the size of the solution (the number of assigned agents or the number of used activities). In particular, finding an individually rational assignment is fixed parameter tractable, yet other solutions concepts are less tractable (W[1]- and W[2]-hard) even under very natural restrictions on inputs.

关键词： parameterized complexity Fixed parameter tractability W-hierarchy Individual rationality Stability Envy-free Agents activity solution concept GASP parameterization

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2018年第7期29卷 1215-1230页

作者： Roayaei, Mehdy Razzazi, MohammadReza Tarbiat Modares Univ Dept Elect & Comp Engn Tehran Iran Amirkabir Univ Technol Dept Comp Engn & Informat Technol Tehran Iran

We consider the directed Steiner network problem, where given a weighted directed graph G and p pairs of vertices P = {(s(1), t(1)), . . . ,(s(p), t(p))}, one has to find the minimum weight subgraph H of G that contains path from s(i) to t(i) for all i. We search for the main cause of the complexity of the problem and introduce the notions of junction vertex and shared segment in an optimal solution. We study the parameterized complexity of the problem with respect to these parameters and achieve several parameterized hardness results. Also, we present two output-sensitive algorithms for the problem, which are much simpler and easier to implement than the previously best known one;and in addition, when the paths corresponding to the input pairs have few shared vertices or arcs in the optimal solution, these algorithms outperform the previous one.

关键词： Directed Steiner network output-sensitive algorithm junction vertex shared segment parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Committee Elections with Dichotomous and Trichotomous Votes 19

Parameterized Complexity of Committee Elections with Dichoto...

引用

Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

作者： Aizhong Zhou Yongjie Yang Jiong Guo Shandong University Qingdao China Central South University Changsha China

ISBN: (纸本)9781450363099

We study the winner determination problem for three prevalent committee election rules: Chamberlin-Courant Approval Voting(CCA), Proportional Approval Voting (PAV), and Satisfaction Approval Voting (SAV). Axiomatic and algorithmic studies of elections under these rules have been conducted recently. It is known that the winner determination problem is NP-hard for CCA and PAV and polynomial-time solvable for SAV, if the input votes are dichotomous. Moreover, parameterized complexity of the two NP-hard cases has been examined with respect to some natural parameters such as the number of candidates or the number of votes. In this paper, we extend the above studies to committee elections with trichotomous votes and identify cases, where trichotomous votes lead to an increase of parameterized complexity. We also consider the maximin (or egalitarian) variations of the rules, where the minimum satisfaction of the voters is maximized.

关键词： maximin committee elections parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On parameterized complexity of the Word Search Problem in the Baumslag-Gersten Group 20

On Parameterized Complexity of the Word Search Problem in th...

引用

45th International Symposium on Symbolic and Algebraic Computation

作者： Miasnikov, Alexei Nikolaev, Andrey Stevens Inst Technol Hoboken NJ 07030 USA

ISBN: (纸本)9781450371001

We consider the word search problem in the BaumslagsGersten group GB. We show that the parameterized complexity of this problem, where the area of van Kampen diagram serves as a parameter, is polynomial in the length of the input and the parameter. This contrasts the well-known result that the Dehn function and the time complexity of the word search problem in GB are non-elementary.

关键词： parameterized complexity fixed parameter tractability word problem word search problem Baumslag-Solitar group Baumslags Gersten group Dehn function

来源：评论

学校读者我要写书评

暂无评论

A note on the parameterized complexity of the maximum independent set problem 8

A note on the parameterized complexity of the maximum indepe...

引用

8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2009

作者： Lozin, Vadim V. DIMAP Mathematics Institute University of Warwick Coventry United Kingdom

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Shift Bribery in Iterative Elections 20

Parameterized Complexity of Shift Bribery in Iterative Elect...

引用

Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems

作者： Aizhong Zhou Jiong Guo Shandong University Qingdao China

ISBN: (纸本)9781450375184

In an iterative voting system, candidates are eliminated in consecutive rounds until either the set of remaining candidates does not change or a fixed number of rounds is reached. In this paper, we consider four prominent iterative voting systems, which are all based on positional scoring rules. The Hare and Coombs systems are based on the plurality and veto rules, respectively, while the Baldwin and Nanson systems are based on the Borda rule. We study the resistance of these four systems against shift bribery. Hereby, we consider both constructive and destructive settings. It is known that all four iterative voting systems are resistant to shift bribery, that is, both constructive and destructive shift bribery problems are NP-hard for these voting systems. We complement these NP-hardness results by examining parameterized complexity of the shift bribery problems with respect to some natural parameters. Our results provide further evidence for the observation that shift bribery problems for iterative voting systems are computationally harder than for the corresponding non-iterative cases. In addition, our reductions apply several techniques which might be useful for proving hardness results for other iterative voting systems.

关键词： iterative elections shift bribery parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Polynomial time approximation schemes and parameterized complexity

引用

29th International Symposium on Mathematical Foundations of Computer Science

作者： Chen, Jianer Huang, Xiuzhen Kanj, Iyad A. Xia, Ge Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA Cent S Univ Coll Informat Sci & Engn Changsha 410083 Peoples R China Arkansas State Univ Dept Comp Sci State Univ AR 72467 USA Depaul Univ Sch CTI Chicago IL 60604 USA Lafayette Coll Dept Comp Sci Easton PA 18042 USA

ISBN: (纸本)3540228233

In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce a notion of polynomial fixed-parameter tractability and prove that, under a very general constraint, an NP optimization problem has a fully polynomial time approximation scheme if and only if the problem is polynomial fixed-parameter tractable. By enforcing a constraint of planarity on the W-hierarchy studied in parameterized complexity theory, we obtain a class of NP optimization problems, the planar W-hierarchy, and prove that all problems in this class have efficient polynomial time approximation schemes (EPTAS). The planar W-hierarchy seems to contain most of the known EPTAS problems, and is significantly different from the class introduced by Khanna and Motwani in their efforts in characterizing optimization problems with polynomial time approximation schemes. (c) 2006 Elsevier B.V. All rights reserved.

关键词： approximation algorithm polynomial time approximation scheme parameterized complexity W-hierarchy

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Multi-winner Determination: More Effort Towards Fixed-Parameter Tractability 18

Parameterized Complexity of Multi-winner Determination: More...

引用

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems

作者： Yongjie Yang Jianxin Wang Saarland University & Central South University Saarbrücken Germany Central South University Changsha China

We study the k -committee selection rules minimax approval, proportional approval, and Chamberlin-Courant's approval. It is known that WINNER DETERMINATION for these rules is NP-hard. Moreover, the parameterized complexity of the problem has also been studied with respect to some natural parameters. However, there are still numerous parameterizations that have not been considered. We revisit the parameterized complexity of WINNER DETERMINATION for these rules by considering several important single parameters, combined parameters, and structural parameters, aiming at detecting as many fixed-parameter tractability results as possible.

关键词： parameterized complexity tree-width approval voting maximum matching multi-winner voting

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：