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

parameterized complexity of team formation in social networks

THEORETICAL COMPUTER SCIENCE 2018年 717卷 26-36页

作者： Bredereck, Robert Chen, Jiehua Hueffner, Falk Kratsch, Stefan TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Univ Oxford Dept Comp Sci Oxford England Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel Univ Bonn Inst Informat 1 Bonn Germany

Given a task that requires some skills and a social network of individuals with differei skills, the TEAM FORMATION problem asks to find a team of individuals that together ca perform the task, while minimizing communication costs. Since the problem is NP-hard, identify the source of intractability by analyzing its parameterized complexity with respel to parameters such as the total number of skills k, the team size 1, the communication cost budget b, and the maximum vertex degree A. We show that the computation complexity strongly depends on the communication cost measure: when using the weight of a minimum spanning tree of the subgraph formed by the selected team, we obtain fixes parameter tractability for example with respect to the parameter k. In contrast, when using the diameter as measure, the problem is intractable with respect to any single parameter however, combining A with either b or 1 yields fixed-parameter tractability. (C) 2017 Elsevier B.V. All rights reserved

关键词： Computational complexity analysis parameterized complexity analysis Team formation on social networks

来源：评论

学校读者我要写书评

暂无评论

Tractable answer-set programming with weight constraints: bounded treewidth is not enough

引用

THEORY AND PRACTICE OF LOGIC PROGRAMMING 2014年第2期14卷 141-164页

作者： Pichler, Reinhard Ruemmele, Stefan Szeider, Stefan Woltran, Stefan Vienna Univ Technol Vienna Austria

Cardinality constraints or, more generally, weight constraints are well recognized as an important extension of answer-set programming. Clearly, all common algorithmic tasks related to programs with cardinality or weight constraints - like checking the consistency of a program - are intractable. Many intractable problems in the area of knowledge representation and reasoning have been shown to become linear time tractable if the treewidth of the programs or formulas under consideration is bounded by some constant. The goal of this paper is to apply the notion of treewidth to programs with cardinality or weight constraints and to identify tractable fragments. It will turn out that the straightforward application of treewidth to such class of programs does not suffice to obtain tractability. However, by imposing further restrictions, tractability can be achieved.

关键词： answer-set programming parameterized complexity analysis treewidth

来源：评论

学校读者我要写书评

暂无评论

The Power of Linear-Time Data Reduction for Maximum Matching

引用

ALGORITHMICA 2020年第12期82卷 3521-3565页

作者： Mertzios, George B. Nichterlein, Andre Niedermeier, Rolf Univ Durham Dept Comp Sci Durham England TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in O(m root n) time;however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.

关键词： Maximum-cardinality matching Bipartite graphs Linear-time algorithms Kernelization parameterized complexity analysis FPT in P

来源：评论

学校读者我要写书评

暂无评论

parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments

引用

INFORMS JOURNAL ON COMPUTING 2022年第1期34卷 55-75页

作者： Bentert, Matthias van Bevern, Rene Nichterlein, Andre Niedermeier, Rolf Smirnov, Pavel V. Tech Univ Berlin Fac 4 Algorithm & Computat Complex D-10587 Berlin Germany Novosibirsk State Univ Dept Mech & Math Novosibirsk 630090 Russia

We study a problem of energy-efficiently connecting a symmetric wireless communication network: given an n-vertex graph with edge weights, find a connected spanning subgraph of minimum cost, where the cost is determined by each vertex paying the heaviest edge incident to it in the subgraph. The problem is known to be NP-hard. Strengthening this hardness result, we show that even o(log n)-approximating the difference d between the optimal solution cost and a natural lower bound is NP-hard. Moreover, we show that under the exponential time hypothesis, there are no exact algorithms running in 2(o(n)) time or in f(d)center dot n(O(1)) time for any computable function f. We also show that the special case of connecting c network components with minimum additional cost generally cannot be polynomial-time reduced to instances of size c(O(1)) unless the polynomial-time hierarchy collapses. On the positive side, we provide an algorithm that reconnects O(log n)-connected components with minimum additional cost in polynomial time. These algorithms are motivated by application scenarios of monitoring areas or where an existing sensor network may fall apart into several connected components because of sensor faults. In experiments, the algorithm outperforms CPLEX with known integer linear programming (ILP) formulations when n is sufficiently large compared with c. Summary of Contribution: Wireless sensor networks are used to monitor air pollution, water pollution, and machine health;in forest fire and landslide detection;and in natural disaster prevention. Sensors in wireless sensor networks are often battery-powered and disposable, so one may be interested in lowering the energy consumption of the sensors in order to achieve a long lifetime of the network. We study the min-power symmetric connectivity problem, which models the task of assigning transmission powers to sensors so as to achieve a connected communication network with minimum total power consumption. The problem is

关键词： connected spanning subgraphs monitoring areas reconnecting sensor networks parameterized complexity analysis approximation hardness parameterization above lower bounds color-coding experimental comparison

来源：评论

学校读者我要写书评

暂无评论

Cluster Editing for Multi-Layer and Temporal Graphs

引用

THEORY OF COMPUTING SYSTEMS 2024年第5期68卷 1239-1290页

作者： Chen, Jiehua Molter, Hendrik Sorge, Manuel Suchy, Ondrej TU Wien Inst Logic & Computat Vienna Austria Ben Gurion Univ Negev Dept Ind Engn & Management Dept Comp Sci Beer Sheva Israel TU Berlin Algorithm & Computat Complex Berlin Germany Czech Tech Univ Fac Informat Technol Prague Czech Republic

Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-Layer Cluster Editing we receive a set of graphs on the same vertex set, called layers and aim to transform all layers into cluster graphs (disjoint unions of cliques) that differ only slightly. More specifically, we want to mark at most d vertices and to transform each layer into a cluster graph using at most k edge additions or deletions per layer so that, if we remove the marked vertices, we obtain the same cluster graph in all layers. In Temporal Cluster Editing we receive a sequence of layers and we want to transform each layer into a cluster graph so that consecutive layers differ only slightly. That is, we want to transform each layer into a cluster graph with at most k edge additions or deletions and to mark a distinct set of d vertices in each layer so that each two consecutive layers are the same after removing the vertices marked in the first of the two layers. We study the combinatorial structure of the two problems via their parameterized complexity with respect to the parameters d and k, among others. Despite the similar definition, the two problems behave quite differently: In particular, Multi-Layer Cluster Editing is fixed-parameter tractable with running time kO(k+d)sO(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k<<^>>{O(k + d)} s<<^>>{O(1)}$$\end{document} for inputs of size s, whereas Temporal Cluster Editing is W[1]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf {W[1]}$$\end{document}-hard with resp

关键词： Time-varying graphs Link streams parameterized complexity analysis Clustering

来源：评论

学校读者我要写书评

暂无评论

Matchings under Preferences: Strength of Stability and Tradeoffs

引用

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION 2021年第4期9卷 1–55页

作者： Chen, Jiehua Skowron, Piotr Sorge, Manuel TU Wien Vienna Austria Univ Warsaw Warsaw Poland

We propose two solution concepts for matchings under preferences: robustness and near stability. The former strengthens while the latter relaxes the classical definition of stability by Gale and Shapley (1962). Informally speaking, robustness requires that a matching must be stable in the classical sense, even if the agents slightly change their preferences. Near stability, however, imposes that a matching must become stable (again, in the classical sense) provided the agents are willing to adjust their preferences a bit. Both of our concepts are quantitative;together they provide means for a fine-grained analysis of the stability of matchings. Moreover, our concepts allow the exploration of tradeoffs between stability and other criteria of social optimality, such as the egalitarian cost and the number of unmatched agents. We investigate the computational complexity of finding matchings that implement certain predefined tradeoffs. We provide a polynomial-time algorithm that, given agent preferences, returns a socially optimal robust matching (if it exists), and we prove that finding a socially optimal and nearly stable matching is computationally hard.

关键词： Stable matchings concepts of stability NP-hardness parameterized complexity analysis exact algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Matchings under Preferences: Strength of Stability and Trade-Offs 19

Matchings under Preferences: Strength of Stability and Trade...

引用

20th ACM Conference on Economics and Computation (ACM EC) held as part of the ACM Federated Computing Research Conference

作者： Chen, Jiehua Skowron, Piotr Sorge, Manuel Univ Warsaw Warsaw Poland

ISBN: (纸本)9781450367929

We propose two solution concepts for matchings under preferences: robustness and near stability. The former strengthens while the latter relaxes the classic definition of stability by Gale and Shapley (1962). Informally speaking, robustness requires that a matching must be stable in the classic sense, even if the agents slightly change their preferences. Near stability, on the other hand, imposes that a matching must become stable (again, in the classic sense) provided the agents are willing to adjust their preferences a bit. Both of our concepts are quantitative;together they provide means for a fine-grained analysis of the stability of matchings. Moreover, our concepts allow the exploration of trade-offs between stability and other criteria of social optimality, such as the egalitarian cost and the number of unmatched agents. We investigate the computational complexity of finding matchings that implement certain predefined trade-offs. We provide a polynomial-time algorithm that, given agent preferences, returns a socially optimal robust matching, and we prove that finding a socially optimal and nearly stable matching is computationally hard.

关键词： Stable matchings concepts of stability NP-hardness parameterized complexity analysis exact algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Group Activity Selection with Few Agent Types 27

Group Activity Selection with Few Agent Types

引用

27th Annual European Symposium on Algorithms (ESA)

作者： Ganian, Robert Ordyniak, Sebastian Rahul, C. S. TU Wien Vienna Austria Univ Sheffield Sheffield S Yorkshire England Univ Warsaw Warsaw Poland

ISBN: (纸本)9783959771245

The Group Activity Selection Problem (GASP) models situations where a group of agents needs to be distributed to a set of activities while taking into account preferences of the agents w.r.t. individual activities and activity sizes. The problem, along with its well-known variants sGASP and gGASP, has previously been studied in the parameterized complexity setting with various parameterizations, such as number of agents, number of activities and solution size. However, the complexity of the problem parameterized by the number of types of agents, a natural parameter proposed already in the first paper that introduced GASP, has so far remained unexplored. In this paper we establish the complexity map for GASP, sGASP and gGASP when the number of types of agents is the parameter. Our positive results, consisting of one fixed-parameter algorithm and one XP algorithm, rely on a combination of novel Subset Sum machinery (which may be of general interest) and identifying certain compression steps which allow us to focus on solutions which are "acyclic". These algorithms are complemented by matching lower bounds, which among others close a gap to a recently obtained tractability result of Gupta, Roy, Saurabh and Zehavi (2017). In this direction, the techniques used to establish W[1]-hardness of sGASP are of particular interest: as an intermediate step, we use Sidon sequences to show the W[1]-hardness of a highly restricted variant of multi-dimensional Subset Sum, which may find applications in other settings as well.

关键词： group activity selection problem parameterized complexity analysis multi-agent systems

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of team formation in social networks 1

引用

11th International Conference on Algorithmic Aspects in Information and Management (AAIM)

ISBN: (数字)9783319411682

ISBN: (纸本)9783319411675

关键词： Computational complexity analysis parameterized complexity analysis Team formation on social networks

来源：评论

学校读者我要写书评

暂无评论

Stable Marriage with Multi-Modal Preferences 18

Stable Marriage with Multi-Modal Preferences

引用

ACM Conference on Economics and Computation (ACM EC)

作者： Chen, Jiehua Niedermeier, Rolf Skowron, Piotr Univ Warsaw Warsaw Poland Ben Gurion Univ Negev Beer Sheva Israel TU Berlin Berlin Germany

ISBN: (纸本)9781450358293

We thoroughly study a generalized version of the famous STABLE MARRIAGE problem, now based on multi-modal preference lists. The central twist herein is to allow each agent to rank its potentially matching counterparts based on more than one "evaluation mode" (e.g., more than one criterion);thus, each agent is equipped with multiple preference lists, each ranking the counterparts in a possibly different way. We introduce and study three natural concepts of stability, investigate their mutual relations and focus on computational complexity aspects with respect to computing stable matchings in these new scenarios. Mostly encountering computational hardness (NP-hardness), we can also spot few islands of tractability and make a surprising connection to the GRAPH ISOMORPHISM problem.

关键词： Stable matching concepts of stability multi-layer (graph) models NP-hardness parameterized complexity analysis exact algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：