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

Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems

作者： Niclas Boehmer Robert Bredereck Klaus Heeger Dušan Knop Junjie Luo TU Berlin Berlin Germany Humboldt-Universität zu Berlin Berlin Germany Czech Technical University in Prague Prague Czech Rep Nanyang Technological University Singapore Singapore

ISBN: (纸本)9781450392136

Fairly dividing a set of indivisible resources to a set of agents is of utmost importance in some applications. However, after an allocation has been implemented the preferences of agents might change and envy might arise. We study the following problem to cope with such situations: Given an allocation of indivisible resources to agents with additive utility-based preferences, is it possible to socially donate some of the resources (which means removing these resources from the allocation instance) such that the resulting modified allocation is envy-free (up to one good). We require that the number of deleted resources and/or the caused utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity of this problem considering various natural and problem-specific parameters (e.g., the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent in the initial allocation) and different preference models, including unary and 0/1-valuations. In our studies, we obtain a rich set of (parameterized) tractability and intractability results and discover several surprising contrasts, for instance, between the two closely related fairness concepts envy-freeness and envy-freeness up to one good and between the influence of the parameters maximum number and welfare of the deleted resources.

关键词： indivisible resources fair allocation donating goods parameterized algorithmics envy-freeness

来源：评论

学校读者我要写书评

暂无评论

A Refined Complexity Analysis of Fair Districting over Graphs 22

A Refined Complexity Analysis of Fair Districting over Graph...

引用

Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems

作者： Niclas Boehmer Tomohiro Koana Rolf Niedermeier TU Berlin Berlin Germany

ISBN: (纸本)9781450392136

We study the NP-hard Fair Connected Districting problem: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios, such as district-based elections, where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. We conduct a fine-grained analysis of the (parameterized) computational complexity of Fair Connected Districting: We study its parameterized complexity with respect to various graph parameters, including treewidth, and problem-specific parameters, including the numbers of colors and districts, and its complexity on graphs from different classes (such as paths, stars, and trees).

关键词： electoral districting vertex-colored graphs parameterized algorithmics

来源：评论

学校读者我要写书评

暂无评论

Exploiting Database Management Systems and Treewidth for Counting 22nd

Exploiting Database Management Systems and Treewidth for Cou...

引用

22nd International Symposium on Practical Aspects of Declarative Languages (PADL)

作者： Fichte, Johannes K. Hecher, Markus Thier, Patrick Woltran, Stefan Tech Univ Dresden Dresden Germany TU Wien Vienna Austria Univ Potsdam Potsdam Germany

ISBN: (纸本)9783030391973;9783030391966

Bounded treewidth is one of the most cited combinatorial invariants, which was applied in the literature for solving several counting problems efficiently. A canonical counting problem is #Sat, which asks to count the satisfying assignments of a Boolean formula. Recent work shows that benchmarking instances for #Sat often have reasonably small treewidth. This paper deals with counting problems for instances of small treewidth. We introduce a general framework to solve counting questions based on state-of-the-art database management systems (DBMS). Our framework takes explicitly advantage of small treewidth by solving instances using dynamic programming (DP) on tree decompositions (TD). Therefore, we implement the concept of DP into a DBMS (PostgreSQL), since DP algorithms are already often given in terms of table manipulations in theory. This allows for elegant specifications of DP algorithms and the use of SQL to manipulate records and tables, which gives us a natural approach to bring DP algorithms into practice. To the best of our knowledge, we present the first approach to employ a DBMS for algorithms on TDs. A key advantage of our approach is that DBMS naturally allow to deal with huge tables with a limited amount of main memory (RAM), parallelization, as well as suspending computation.

关键词： Dynamic programming parameterized algorithmics Bounded treewidth Database systems SQL Relational algebra Counting

来源：评论

学校读者我要写书评

暂无评论

An Improved GPU-Based SAT Model Counter 25th

An Improved GPU-Based SAT Model Counter

引用

25th International Conference on the Principles and Practice of Constraint Programming (CP)

作者： Fichte, Johannes K. Hecher, Markus Zisser, Markus Tech Univ Dresden Dresden Germany TU Wien Vienna Austria Univ Potsdam Potsdam Germany

ISBN: (纸本)9783030300487

In this paper, we present and evaluate a new parallel propositional model counter, called gpusat2, which is based on dynamic programming (DP) on tree decompositions using log-counters. gpusat2 extends its predecessor by a novel architecture for DP that includes using customized tree decompositions, storing solutions to parts of the input instance during the computation variably in arrays or binary search trees, and compressing solution parts. In addition, we avoid data transfer between the RAM and the VRAM whenever possible and employ extended preprocessing by means of state-of-the-art preprocessors for propositional model counting. Our novel architecture allows gpusat2 to be competitive with modern model counters when we also take preprocessing into consideration. As a side result, we observe that state-of-the-art preprocessors allow to produce tree decompositions of significantly smaller width.

关键词： Propositional model counting Dynamic programming parameterized algorithmics Bounded treewidth

来源：评论

学校读者我要写书评

暂无评论

Theoretical and empirical evaluation of data reduction for exact Kemeny Rank Aggregation

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2014年第5期28卷 721-748页

作者： Betzler, Nadja Bredereck, Robert Niedermeier, Rolf TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

Kemeny Rank Aggregation is a consensus finding problem important in many areas ranging from classical voting over web search and databases to bioinformatics. The underlying decision problem Kemeny Score is NP-complete even in case of four input rankings to be aggregated into a "median ranking". We analyze efficient polynomial-time data reduction rules with provable performance bounds that allow us to find even all optimal median rankings. We show that our reduced instances contain at most candidates where denotes the average Kendall's tau distance between the input votes. On the theoretical side, this improves a corresponding result for a "partial problem kernel" from quadratic to linear size. In this context we provide a theoretical analysis of a commonly used data reduction. On the practical side, we provide experimental results with data based on web search and sport competitions, e.g., computing optimal median rankings for real-world instances with more than 100 candidates within milliseconds. Moreover, we perform experiments with randomly generated data based on two random distribution models for permutations.

关键词： Kemeny score NP-hardness parameterized algorithmics Preprocessing Average parameterization Partial problem kernel Experiments

来源：评论

学校读者我要写书评

暂无评论

The effect of homogeneity on the computational complexity of combinatorial data anonymization

引用

DATA MINING AND KNOWLEDGE DISCOVERY 2014年第1期28卷 65-91页

作者： Bredereck, Robert Nichterlein, Andre Niedermeier, Rolf Philip, Geevarghese TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Max Planck Inst Informat D-66123 Saarbrucken Germany

A matrix M is said to be k-anonymous if for each row r in M there are at least k - 1 other rows in M which are identical to r. The NP-hard k-Anonymity problem asks, given an n x m-matrix M over a fixed alphabet and an integer s > 0, whether M can be made k-anonymous by suppressing (blanking out) at most s entries. Complementing previous work, we introduce two new "data-driven" parameterizations for k-Anonymity-the number t (in) of different input rows and the number t (out) of different output rows-both modeling aspects of data homogeneity. We show that k-Anonymity is fixed-parameter tractable for the parameter t (in) , and that it is NP-hard even for t (out) = 2 and alphabet size four. Notably, our fixed-parameter tractability result implies that k-Anonymity can be solved in linear time when t (in) is a constant. Our computational hardness results also extend to the related privacy problems p-Sensitivity and a""-Diversity, while our fixed-parameter tractability results extend to p-Sensitivity and the usage of domain generalization hierarchies, where the entries are replaced by more general data instead of being completely suppressed.

关键词： k-Anonymity p-Sensitivity l-Diversity Domain generalization hierarchies Matrix modification problems parameterized algorithmics Fixed-parameter tractability NP-hardness

来源：评论

学校读者我要写书评

暂无评论

Towards Optimal and Expressive Kernelization for d-Hitting Set

引用

ALGORITHMICA 2014年第1期70卷 129-147页

作者： van Bevern, Rene TU Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany

A sunflower in a hypergraph is a set of hyperedges pairwise intersecting in exactly the same vertex set. Sunflowers are a useful tool in polynomial-time data reduction for problems formalizable as d-Hitting Set, the problem of covering all hyperedges (whose cardinality is bounded from above by a constant d) of a hypergraph by at most k vertices. Additionally, in fault diagnosis, sunflowers yield concise explanations for "highly defective structures". We provide a linear-time algorithm that, by finding sunflowers, transforms an instance of d-Hitting Set into an equivalent instance comprising at most O(k (d) ) hyperedges and vertices. In terms of parameterized complexity, we show a problem kernel with asymptotically optimal size (unless ) and provide experimental results that show the practical applicability of our algorithm. Finally, we show that the number of vertices can be reduced to O(k (d-1)) with additional processing in O(k (1.5d) ) time-nontrivially combining the sunflower technique with problem kernels due to Abu-Khzam and Moser.

关键词： parameterized algorithmics Linear-time data reduction Vertex cover in hypergraphs Fault diagnosis Sunflower lemma Algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Confluence in Data Reduction: Bridging Graph Transformation and Kernelization

引用

COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE 2013年第1期2卷 31-49页

作者： Ehrig, Hartmut Ermel, Claudia Hueffner, Falk Niedermeier, Rolf Runge, Olga Inst Softwaretechnik & Theoret Informat TU Berlin Sekr MAR 5-5Marchstr 23 D-10587 Berlin Germany

Kernelization is a core tool of parameterized algorithmics for coping with computationally intractable problems. A kernelization reduces in polynomial time an input instance to an equivalent instance whose size is bounded by a function only depending on some problem-specific parameter k;this new instance is called problem kernel. Typically, problem kernels are achieved by performing efficient data reduction rules. So far, there was little systematic study in the literature concerning the mutual interaction of data reduction rules, in particular whether data reduction rules for a specific problem always lead to the same reduced instance, no matter in which order the rules are applied. This corresponds to the concept of confluence from the theory of rewriting systems. We argue that it is valuable to study whether a kernelization is confluent, using the NP-hard graph problems (EDGE) CLIQUE COVER and PARTIAL CLIQUE COVER as running examples. We apply the concept of critical pair analysis from graph transformation theory, supported by the AGG software tool. These results support the main goal of our work, namely, to establish a fruitful link between (parameterized) algorithmics and graph transformation theory, two so far unrelated fields.

关键词： parameterized algorithmics problem kernel formal methods critical pair analysis confluence

来源：评论

学校读者我要写书评

暂无评论

Exact combinatorial algorithms and experiments for finding maximum k-plexes

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2012年第3期24卷 347-373页

作者： Moser, Hannes Niedermeier, Rolf Sorge, Manuel TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

We propose new practical algorithms to find maximum-cardinality k-plexes in graphs. A k-plex denotes a vertex subset in a graph inducing a subgraph where every vertex has edges to all but at most k vertices in the k-plex. Cliques are 1-plexes. In analogy to the special case of finding maximum-cardinality cliques, finding maximum-cardinality k-plexes is NP-hard. Complementing previous work, we develop exact combinatorial algorithms, which are strongly based on methods from parameterized algorithmics. The experiments with our freely available implementation indicate the competitiveness of our approach, for many real-world graphs outperforming the previously used methods.

关键词： parameterized algorithmics Social network analysis Biological network analysis NP-complete graph problems Dense subgraphs s-plexes k-dependent sets

来源：评论

学校读者我要写书评

暂无评论

Cluster editing with locally bounded modifications

引用

DISCRETE APPLIED MATHEMATICS 2012年第15期160卷 2259-2270页

作者： Komusiewicz, Christian Uhlmann, Johannes TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

Given an undirected graph G = (V, E) and a nonnegative integer k, the NP-hard CLUSTER EDITING problem asks whether G can be transformed into a disjoint union of cliques by modifying at most k edges. In this work, we study how "local degree bounds" influence the complexity Of CLUSTER EDITING and of the related CLUSTER DELETION problem which allows only edge deletions. We show that even for graphs with constant maximum degree CLUSTER EDITING and CLUSTER DELETION are NP-hard and that this implies NP-hardness even if every vertex is incident with only a constant number of edge modifications. We further show that under some complexity-theoretic assumptions both CLUSTER EDITING and CLUSTER DELETION cannot be solved within a running time that is subexponential in k, vertical bar V vertical bar, or vertical bar E vertical bar. Finally, we present a problem kernelization for the combined parameter "number d of clusters and maximum number t of modifications incident with a vertex" thus showing that CLUSTER EDITING and CLUSTER DELETION become easier in case the number of clusters is upper-bounded. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Graph modification problems parameterized algorithmics Exponential-time hypothesis Data reduction

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：