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

Stable Matchings with Restricted Preferences: Structure and Complexity

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION 2022年第3期10卷 13-13页

作者： Cheng, Christine T. Rosenbaum, Will Univ Wisconsin 3200 N Cramer Ave Milwaukee WI 53211 USA Amherst Coll POB 5000 Amherst MA 01002 USA

In the stable marriage (SM) problem, there are two sets of agents-traditionally referred to as men and women-and each agent has a preference list that ranks (a subset of) agents of the opposite sex. The goal is to find a matching between men and women that is stable in the sense that no man-woman pair mutually prefers each other to their assigned partners. In a seminal work, Gale and Shapley [16] showed that stable matchings always exist and described an efficient algorithm for finding one. Irving and Leather [24] defined the rotation poset of an SM instance and showed that it determines the structure of the set of stable matchings of the instance. They further showed that every finite poset can be realized as the rotation poset of some SM instance. Consequently, many problems-such as counting stable matchings and finding certain "fair" stable matchings-are computationally intractable (NP-hard) in general. In this article, we consider SM instances in which certain restrictions are placed on the preference lists. We show that three natural preference models-k-bounded, k-attribute, and (k(1), k(2))-list-can realize arbitrary rotation posets for constant values of k. Hence, even in these highly restricted preference models, many stable matching problems remain intractable. In contrast, we show that for any fixed constant k, the rotation posets of k-range instances are highly restricted. As a consequence, we show that exactly counting and uniformly sampling stable matchings, finding median, sex-equal, and balanced stable matchings, are fixed-parameter tractable when parameterized by the range of the instance. Thus, these problems can be solved in polynomial time on instances of the k-range model for any fixed constant k.

关键词： Stable matchings restricted preferences parameterized algorithms parameterized complexity rotation poset

来源：评论

学校读者我要写书评

暂无评论

DynASP2.5: Dynamic Programming on Tree Decompositions in Action

引用

algorithms 2021年第3期14卷 81-81页

作者： Fichte, Johannes K. Hecher, Markus Morak, Michael Woltran, Stefan Univ Calif Berkeley Simons Inst Theory Comp Berkeley CA 94720 USA TU Wien Inst Log & Computat A-1040 Vienna Austria Univ Potsdam Inst Comp Sci D-14482 Potsdam Germany AAU Klagenfurt Inst Artificial Intelligence & Cybersecur A-9020 Klagenfurt Austria

Efficient exact parameterized algorithms are an active research area. Such algorithms exhibit a broad interest in the theoretical community. In the last few years, implementations for computing various parameters (parameter detection) have been established in parameterized challenges, such as treewidth, treedepth, hypertree width, feedback vertex set, or vertex cover. In theory, instances, for which the considered parameter is small, can be solved fast (problem evaluation), i.e., the runtime is bounded exponential in the parameter. While such favorable theoretical guarantees exists, it is often unclear whether one can successfully implement these algorithms under practical considerations. In other words, can we design and construct implementations of parameterized algorithms such that they perform similar or even better than well-established problem solvers on instances where the parameter is small. Indeed, we can build an implementation that performs well under the theoretical assumptions. However, it could also well be that an existing solver implicitly takes advantage of a structure, which is often claimed for solvers that build on SAT-solving. In this paper, we consider finding one solution to instances of answer set programming (ASP), which is a logic-based declarative modeling and solving framework. Solutions for ASP instances are so-called answer sets. Interestingly, the problem of deciding whether an instance has an answer set is already located on the second level of the polynomial hierarchy. An ASP solver that employs treewidth as parameter and runs dynamic programming on tree decompositions is DynASP2. Empirical experiments show that this solver is fast on instances of small treewidth and can outperform modern ASP when one counts answer sets. It remains open, whether one can improve the solver such that it also finds one answer set fast and shows competitive behavior to modern ASP solvers on instances of low treewidth. Unfortunately, theoretical models of

关键词： parameterized algorithms fixed-parameter linear time semi-incidence graph tree decompositions multi-pass dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Min-max coverage problems on tree-like metrics

引用

Procedia Computer Science 2023年 223卷 148-156页

作者： Eric Aaron Úrsula Hébert-Johnson Danny Krizanc Daniel Lokshtanov Colby College Waterville ME 04901 USA University of California Santa Barbara 93106 USA Wesleyan University Middletown CT 06457 USA

We consider a number of min-max coverage problems. In each problem, the input is an unweighted graph G and an integer k, and possibly some additional information, such as a root vertex r. In the Min-Max Path Cover problem, the task is to cover all vertices of the graph by k walks, minimizing the length of the longest walk. The variant of Min-Max Path Cover in which all walks start and end at the same prescribed root vertex r is called the k-Traveling Salesmen Problem. In the Min-Max Tree Cover problem, the task is to cover all vertices of the graph by k trees, minimizing the size (number of edges) of the largest tree. In the rooted version, Min-Max k-Rooted Tree Cover, the input also contains k roots r 1 , . . ., r k , and the i th tree must contain the root r i . These four problems are all known to be APX-hard and to admit a constant-factor approximation. In this paper, we initiate the systematic study of these problems on trees and, more generally, on graphs of constant treewidth. As opposed to most graph problems, all four of the above coverage problems remain NP-hard even when G is a tree. We obtain an n O(k) -time exact algorithm for all four problems on graphs of bounded treewidth. Our main contribution is a quasi-polynomial-time approximation scheme (QPTAS) for the k-Traveling Salesmen Problem, Min-Max Path Cover, and Min-Max Tree Cover on graphs of bounded treewidth.

关键词： Approximation algorithms parameterized algorithms Min-max coverage Treewidth Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

Tractable Parameterizations for the Minimum Linear Arrangement Problem

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2016年第2期8卷 6-6页

作者： Fellows, Michael R. Hermelin, Danny Rosamond, Frances Shachnai, Hadas Univ Bergen Dept Informat POB 7803 N-5020 Bergen Norway Ben Gurion Univ Negev Dept Ind Engn & Management Marcus Family CampusPOB 653 IL-8410501 Beer Sheva Israel Technion Israel Inst Technol Dept Comp Sci IL-3200003 Haifa Israel

The MINIMUM LINEAR ARRANGEMENT (MLA) problem involves embedding a given graph on the integer line so that the sum of the edge lengths of the embedded graph is minimized. Most layout problems are either intractable or not known to be tractable, parameterized by the treewidth of the input graph. We investigate MLA with respect to three parameters that provide more structure than treewidth. In particular, we give a factor (1+epsilon)-approximation algorithm for MLA parameterized by (epsilon, k), where k is the vertex cover number of the input graph. By a similar approach, we obtain two FPT algorithms that exactly solve MLA parameterized by, respectively, the max leaf and edge clique cover numbers of the input graph.

关键词： Minimum linear arrangement parameterized algorithms fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Expansion Lemma-Variations and Applications to Polynomial-Time Preprocessing

引用

algorithms 2023年第3期16卷 144-144页

作者： Jacob, Ashwin Majumdar, Diptapriyo Raman, Venkatesh Ben Gurion Univ Negev Dept Comp Sci IL-8410501 Beer Sheva Israel Indraprastha Inst Informat Technol Delhi New Delhi 110020 India HBNI Inst Math Sci Chennai 600113 India

In parameterized complexity, it is well-known that a parameterized problem is fixed-parameter tractable if and only if it has a kernel-an instance equivalent to the input instance, whose size is just a function of the parameter. The size of the kernel can be exponential or worse, resulting in a quest for fixed-parameter tractable problems with polynomial-sized kernels. The developments in machinery (showing lower bounds for the sizes of the kernels) have led researchers to question what are the asymptotically optimum sizes for the kernels of fixed-parameter tractable problems. In this article, we surveyed a tool called expansion lemma that helps in reducing the size of the kernel. Its early origin was in the form of crown decomposition, i.e., to obtain the linear kernel for the Vertex Cover problem;the specific lemma was identified as the tool behind the optimal O(k(2)) kernel for the undirected feedback vertex set problem. Since then, several variations and extensions of the tool have been discovered. We surveyed them along with their applications in this article.

关键词： parameterized algorithms kernelization expansion lemma crown decomposition

来源：评论

学校读者我要写书评

暂无评论

A note on clustering aggregation for binary clusterings

引用

OPERATIONS RESEARCH LETTERS 2024年 52卷

作者： Chen, Jiehua Hermelin, Danny Sorge, Manuel TU Wien Inst Log & Computat Vienna Austria Ben Gurion Univ Negev Beer Sheva Israel TU Wien Favoritenstr 9-11 A-1040 Vienna Austria

We consider the clustering aggregation problem in which we are given a set of clusterings and want to find an aggregated clustering which minimizes the sum of mismatches to the input clusterings. In the binary case (each clustering is a bipartition) this problem was known to be NP-hard under Turing reductions. We strengthen this result by providing a polynomial-time many-one reduction. Our result also implies that no 2o(n)center dot |I'|O(1)-time algorithm exists that solves any given clustering instance I' with n elements, unless the Exponential Time Hypothesis fails. On the positive side, we show that the problem is fixed-parameter tractable with respect to the number of input clusterings.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Aggregation of binary strings Mirkin distance minimization Median procedure parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Budget-feasible Egalitarian Allocation of Conflicting Jobs 24

Budget-feasible Egalitarian Allocation of Conflicting Jobs

引用

Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems

作者： Sushmita Gupta Pallavi Jain A Mohanapriya Vikash Tripathi The Institute of Mathematical Science Chennai India Indian Institute of Technology Jodhpur Jodhpur India The Institute of Mathematical Sciences Chennai India

ISBN: (纸本)9798400704864

Allocating conflicting jobs among individuals while respecting a budget constraint for each individual is an optimization problem that arises in various real-world scenarios. In this paper, we consider the situation where each individual derives some satisfaction from each job. We focus on finding a feasible allocation of conflicting jobs that maximize egalitarian cost, i.e. the satisfaction of the individual who is worst-off. To the best of our knowledge, this is the first paper to combine egalitarianism, budget-feasibility, and conflict-freeness in allocations. We provide a systematic study of the computational complexity of finding budget-feasible conflict-free egalitarian allocation and show that our problem generalizes a large number of classical optimization problems. Therefore, unsurprisingly, our problem is NP-Hard even for two individuals and when there is no conflict between any jobs. We show that the problem admits algorithms when studied in the realm of approximation algorithms and parameterized algorithms with a host of natural parameters that match and in some cases improve upon the running time of known algorithms.

关键词： approximation algorithms fair allocation maximize egalitarian cost parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Iterative Expansion and Color Coding: An Improved Algorithm for 3D-Matching

引用

ACM TRANSACTIONS ON algorithms 2012年第1期8卷 6-6页

作者： Chen, Jianer Liu, Yang Lu, Songjian Sze, Sing-Hoi Zhang, Fenghui Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Univ Texas Pan Amer Dept Comp Sci Edinburg TX 78539 USA Med Univ S Carolina Dept Biochem & Mol Biol Charleston SC 29425 USA Google Inc Seattle WA 98103 USA

The research in the parameterized 3D-MATCHING problem has yielded a number of new algorithmic techniques and an impressive list of improved algorithms. In this article, a new deterministic algorithm for the problem is developed that integrates and improves a number of known techniques, including greedy localization, dynamic programming, and color coding. The new algorithm, which either constructs a matching of k triples in a given triple set or correctly reports that no such a matching exists, runs in time O*(2.80(3k)), improving a long list of previous algorithms for the problem.

关键词： Color coding dynamic programming matching parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs

引用

ACM Transactions on algorithms 1000年

作者： Jacob Focke Dániel Marx Fionn Mc Inerney Daniel Neuen Govind S. Sankar Philipp Schepper Philip Wellnitz CISPA Helmholtz Center for Information Security Germany Algorithms and Complexity Group TU Wien Austria Max Planck Institute for Informatics Saarland Informatics Campus Germany Duke University US National Institute of Informatics and The Graduate University for Advanced Studies SOKENDAI Japan

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets \(\sigma,\rho\) of non-negative integers, a \((\sigma,\rho)\)-set of a graph \(G\) is a set \(S\) of vertices such that \(|N(u)\cap S|\in\sigma\) for every \(u\in S\), and \(|N(v)\cap S|\in\rho\) for every \(v\not\in S\). The problem of finding a \((\sigma,\rho)\)-set (of a certain size) unifies standard problems such as Independent Set, Dominating Set, Independent Dominating Set, and many *** all pairs of finite or cofinite sets \((\sigma,\rho)\), we determine (under standard complexity assumptions) the best possible value \(c_{\sigma,\rho}\) such that there is an algorithm that counts \((\sigma,\rho)\)-sets in time \(c_{\sigma,\rho}^{\rm{tw}} \cdot n^{O(1)}\) (if a tree decomposition of width \(\rm{tw}\) is given in the input). Let \(s_{\rm{top}}\) denote the largest element of \(\sigma\) if \(\sigma\) is finite, or the largest missing integer \(+1\) if \(\sigma\) is cofinite; \(r_{\rm{top}}\) is defined analogously for \(\rho\). Surprisingly, \(c_{\sigma,\rho}\) is often significantly smaller than the natural bound \(s_{\rm{top}}+r_{\rm{top}}+2\) achieved by existing algorithms [van Rooij, 2020]. Toward defining \(c_{\sigma,\rho}\), we say that \((\sigma,\rho)\) is m-structured if there is a pair \((\alpha,\beta)\) such that every integer in \(\sigma\) equals \(\alpha\) mod m, and every integer in \(\rho\) equals \(\beta\) mod m. Then, setting—\(c_{\sigma,\rho}=s_{\rm{top}}+r_{\rm{top}}+2\) if \((\sigma,\rho)\) is not m-structured for any \(\rm{m}\geq 2\),—\(c_{\sigma,\rho}=\max\{s_{\rm{top}},r_{\rm{top}}\}+2\) if \((\sigma,\rho)\) is 2-structured, but not \(\rm{m}\)-structured for any \(\rm{m}\geq 3\), and \(s_{\rm{top}}=r_{\rm{top}}\) is even, and—\(c_{\sigma,\rho}=\max\{s_{\rm{top}},r_{\rm{top}}\}+1\), otherwise,we provide algorithms counting \((\sigma,\rho)\)-sets in time \(c_{\sigma,\rho}^{\rm{tw}}\cdot n^{O(1)}\). For e

关键词： dominating set independent set parameterized algorithms treewidth

来源：评论

学校读者我要写书评

暂无评论

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results

引用

ACM Transactions on Computation Theory 1000年

作者： Jacob Focke Dániel Marx Fionn Mc Inerney Daniel Neuen Govind S. Sankar Philipp Schepper Philip Wellnitz CISPA Helmholtz Center for Information Security Saarbrucken Germany CISPA Helmholtz Center for Information Security Saarbrucken Germany Algorithms and Complexity Group TU Wien Vienna Austria Max Planck Institute for Informatics Saarland Informatics Campus Saarbrucken Germany Duke University Durham United States National Institute of Informatics Tokyo Japan The Graduate University for Advanced Studies Tokyo Japan

For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that |N(u)∩S| ∈ σ for every u ∈ S, and |N(v)∩S| ∈ ρ for every \(v\not\in S\). The problem of finding a (σ, ρ)-set (of a certain size) unifies common problems like Independent Set, Dominating Set, Independent Dominating Set, and many *** an accompanying paper, it is proven that, for all pairs of finite or cofinite sets (σ, ρ), there is an algorithm that counts (σ, ρ)-sets in time \((c_{\sigma,\rho })^{\sf tw}\cdot n^{{\rm O}(1)}\) (if a tree decomposition of width \({\sf tw}\) is given in the input). Here, cσ, ρ is a constant with an intricate dependency on σ and ρ. Despite this intricacy, we show that the algorithms in the accompanying paper are most likely optimal, i.e., for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any ε > 0, a \((c_{\sigma,\rho }-\varepsilon)^{\sf tw}\cdot n^{{\rm O}(1)}\)-algorithm counting the number of (σ, ρ)-sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets σ and ρ, our lower bounds also extend to the decision version, showing that those algorithms are optimal in this setting as well.

关键词： Dominating Set Independent Set parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：