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

30th International Conference on Principles and Practice of Constraint Programming, CP 2024

作者： Kirchweger, Markus Szeider, Stefan Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959773362

Envy-freeness up to any good (EFX) is a key concept in Computational Social Choice for the fair division of indivisible goods, where no agent envies another's allocation after removing any single item. A deeper understanding of EFX allocations is facilitated by exploring the rainbow cycle number (Rf (d)), the largest number of independent sets in a certain class of directed graphs. Upper bounds on Rf (d) provide guarantees to the feasibility of EFX allocations (Chaudhury et al., EC 2021). In this work, we precisely compute the numbers Rf (d) for small values of d, employing the SAT modulo Symmetries framework (Kirchweger and Szeider, CP 2021). SAT modulo Symmetries is tailored specifically for the constraint-based isomorph-free generation of combinatorial structures. We provide an efficient encoding for the rainbow cycle number, comparing eager and lazy approaches. To cope with the huge search space, we extend the encoding with invariant pruning, a new method that significantly speeds up computation. © Markus Kirchweger and Stefan Szeider.

关键词： Encoding (symbols)

来源：评论

学校读者我要写书评

暂无评论

The Parameterized complexity Of Extending Stack Layouts 32

The Parameterized Complexity Of Extending Stack Layouts

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Depian, Thomas Fink, Simon D. Ganian, Robert Nöllenburg, Martin Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959773430

An -page stack layout (also known as an -page book embedding) of a graph is a linear order of the vertex set together with a partition of the edge set into stacks (or pages), such that the endpoints of no two edges on the same stack alternate. We study the problem of extending a given partial -page stack layout into a complete one, which can be seen as a natural generalization of the classical NP-hard problem of computing a stack layout of an input graph from scratch. Given the inherent intractability of the problem, we focus on identifying tractable fragments through the refined lens of parameterized complexity analysis. Our results paint a detailed and surprisingly rich complexity-theoretic landscape of the problem which includes the identification of paraNP-hard, W[1]-hard and XP-tractable, as well as fixed-parameter tractable fragments of stack layout extension via a natural sequence of parameterizations. © Thomas Depian, Simon D. Fink, Robert Ganian, and Martin Nöllenburg.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Small Unsatisfiable k-CNFs with Bounded Literal Occurrence 27

Small Unsatisfiable k-CNFs with Bounded Literal Occurrence

引用

27th International Conference on Theory and Applications of Satisfiability Testing, SAT 2024

作者： Zhang, Tianwei Peitl, Tomáš Szeider, Stefan Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959773348

We obtain the smallest unsatisfiable formulas in subclasses of k-CNF (exactly k distinct literals per clause) with bounded variable or literal occurrences. Smaller unsatisfiable formulas of this type translate into stronger inapproximability results for MaxSAT in the considered formula class. Our results cover subclasses of 3-CNF and 4-CNF;in all subclasses of 3-CNF we considered we were able to determine the smallest size of an unsatisfiable formula;in the case of 4-CNF with at most 5 occurrences per variable we decreased the size of the smallest known unsatisfiable formula. Our methods combine theoretical arguments and symmetry-breaking exhaustive search based on SAT Modulo Symmetries (SMS), a recent framework for isomorph-free SAT-based graph generation. To this end, and as a standalone result of independent interest, we show how to encode formulas as graphs efficiently for SMS. © Tianwei Zhang, Tomáš Peitl, and Stefan Szeider.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Large and Parallel Human Sorting Networks 7th

Large and Parallel Human Sorting Networks

引用

7th International Conference on Creative Mathematical Sciences Communication, CMSC 2024

作者： Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783031732560

This paper presents two innovative extensions of the classic Human Sorting Network (HSN) activity from the CS Unplugged program. First, we describe the implementation of a large-scale HSN with 50 input nodes, realized with high school students in Vienna, Austria. We detail the logistical challenges and solutions for creating an HSN of this magnitude, including location selection, network layout, and participant coordination. Second, we report on using parallel 6-input HSNs, which introduce a competitive element and enhance engagement. This parallel setup allows for races between teams and can be adapted for various age groups and knowledge levels. Both extensions aim to increase the educational impact and enjoyment of the HSN activity. We provide comprehensive insights into our experiences, enabling other educators and researchers to replicate or further develop these HSN variants. © The Author(s) 2025.

关键词： algorithmic education Computational Thinking CS Unplugged Human sorting networks large-scale computing activities parallel sorting algorithms

来源：评论

学校读者我要写书评

暂无评论

On the Relative Efficiency of Dynamic and Static Top-Down Compilation to Decision-DNNF 27

On the Relative Efficiency of Dynamic and Static Top-Down Co...

引用

27th International Conference on Theory and Applications of Satisfiability Testing, SAT 2024

作者： de Colnet, Alexis Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959773348

Top-down compilers of CNF formulas to circuits in decision-DNNF (Decomposable Negation Normal Form) have proved to be useful for model counting. These compilers rely on a common set of techniques including DPLL-style exploration of the set of models, caching of residual formulas, and connected components detection. Differences between compilers lie in the variable selection heuristics and in the additional processing techniques they may use. We investigate, from a theoretical perspective, the ability of top-down compilation algorithms to find small decision-DNNF circuits for two different variable selection strategies. Both strategies are guided by a graph of the CNF formula and are inspired by what is done in practice. The first uses a dynamic graph-partitioning approach while the second works with a static tree decomposition. We show that the dynamic approach performs significantly better than the static approach for some formulas, and that the opposite also holds for other formulas. Our lower bounds are proved despite loose settings where the compilation algorithm is only forced to follow its designed variable selection strategy and where everything else, including the many opportunities for tie-breaking, can be handled non-deterministically. © Alexis de Colnet.

关键词： Program compilers

来源：评论

学校读者我要写书评

暂无评论

Structure-Guided Local Improvement for Maximum Satisfiability 30

Structure-Guided Local Improvement for Maximum Satisfiabilit...

引用

30th International Conference on Principles and Practice of Constraint Programming, CP 2024

作者： Schidler, André Szeider, Stefan Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959773362

The enhanced performance of today's MaxSAT solvers has elevated their appeal for many large-scale applications, notably in software analysis and computer-aided design. Our research delves into refining anytime MaxSAT solving by repeatedly identifying and solving with an exact solver smaller subinstances that are chosen based on the graphical structure of the instance. We investigate various strategies to pinpoint these subinstances. This structure-guided selection of subinstances provides an exact solver with a high potential for improving the current solution. Our exhaustive experimental analyses contrast our methodology as instantiated in our tool MaxSLIM with previous studies and benchmark it against leading-edge MaxSAT solvers. © André Schidler and Stefan Szeider.

关键词： graphical structure incomplete MaxSAT large neighborhood search (LNS) maximum satisfiability metaheuristic SAT-based local improvement (SLIM)

来源：评论

学校读者我要写书评

暂无评论

MosaicSets: Embedding Set Systems into Grid Graphs

引用

IEEE Transactions on Visualization and Computer Graphics 2023年第1期29卷 875-885页

作者： Rottmann, Peter Wallinger, Markus Bonerath, Annika Gedicke, Sven Nollenburg, Martin Haunert, Jan-Henrik Geoinformation Group University of Bonn Germany Algorithms and Complexity Group Technical University of Vienna Austria

Visualizing sets of elements and their relations is an important research area in information visualization. In this paper, we present MosaicSets: a novel approach to create Euler-like diagrams from non-spatial set systems such that each element occupies one cell of a regular hexagonal or square grid. The main challenge is to find an assignment of the elements to the grid cells such that each set constitutes a contiguous region. As use case, we consider the research groups of a university faculty as elements, and the departments and joint research projects as sets. We aim at finding a suitable mapping between the research groups and the grid cells such that the department structure forms a base map layout. Our objectives are to optimize both the compactness of the entirety of all cells and of each set by itself. We show that computing the mapping is NP-hard. However, using integer linear programming we can solve real-world instances optimally within a few seconds. Moreover, we propose a relaxation of the contiguity requirement to visualize otherwise non-embeddable set systems. We present and discuss different rendering styles for the set overlays. Based on a case study with real-world data, our evaluation comprises quantitative measures as well as expert interviews. © 2022 IEEE.

关键词： Visualization

来源：评论

学校读者我要写书评

暂无评论

The Power of Collaboration: Learning Large Bayesian Networks at Scale 36

The Power of Collaboration: Learning Large Bayesian Networks...

引用

36th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2024

作者： Ramaswamy, Vaidyanathan Peruvemba Szeider, Stefan Xia, Hai Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9798331527235

We present a novel approach to learn the structure of large Bayesian Networks (BNs) of bounded treewidth. Our approach combines the complementary strengths of heuristic and MaxSAT-based methods. Both methods operate in parallel and cooperate in a mutually advantageous way to improve the quality of the learned BN structures. Our work utilizes an approach proposed by Peruvemba Ramaswamy and Szeider (AAAI'21, NeurIPS'21, UAI'22), which continually applies a MaxSAT-based algorithm to a BN obtained from heuristic search. We create a continuous and dynamic refinement process by allowing the heuristic and the MaxSAT-based technique to cooperate and repeatedly share their work. Our rigorous experiments show that the collaboration between the two methods is a powerful strategy for increasing the score of the learned BN structure. Moreover, the rate at which the score increases is significantly higher than that of the individual methods by themselves. Our results provide a strong argument for combining complementary approaches to learn treewidth-bounded BNs in a collaborative way. © 2024 IEEE.

关键词： Bayesian networks

来源：评论

学校读者我要写书评

暂无评论

ASP-QRAT: a Conditionally Optimal Dual Proof System for ASP 21

ASP-QRAT: a Conditionally Optimal Dual Proof System for ASP

引用

21st International Conference on Principles of Knowledge Representation and Reasoning, KR 2024

作者： Chew, Leroy de Colnet, Alexis Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9781956792058

Answer Set Programming (ASP) is a declarative programming approach that captures many problems in knowledge representation and reasoning. To certify an ASP solver’s decision, whether the program is consistent or inconsistent, we need a certificate or proof that can be independently verified. This paper proposes the dual proof system ASP-QRAT that certifies consistent and inconsistent ASPs. ASP-QRAT is based on a translation of ASP to QBF (Quantified Boolean Formulas) and the QBF proof system QRAT as a checking format. We show that ASP-QRAT p-simulates ASP-DRUPE, an existing refutation system for inconsistent disjunctive ASPs. We show that ASP-QRAT is conditionally optimal for consistent and inconsistent ASPs, i.e., any super-polynomial lower bound on the shortest proof size of ASP-QRAT implies a major breakthrough in theoretical computer science. The case for consistent ASPs is remarkable because no analog exists in the QBF case. © 2024 Proceedings of the International Conference on Knowledge Representation and Reasoning. All rights reserved.

关键词： Knowledge representation

来源：评论

学校读者我要写书评

暂无评论

The complexity of Optimizing Atomic Congestion 38

The Complexity of Optimizing Atomic Congestion

引用

38th AAAI Conference on Artificial Intelligence, AAAI 2024

作者： Brand, Cornelius Ganian, Robert Kalyanasundaram, Subrahmanyam Inerney, Fionn Mc Algorithms & Complexity Theory Group Regensburg University Germany Algorithms and Complexity Group TU Wien Austria Department of Computer Science and Engineering IIT Hyderabad India

ISBN: (纸本)1577358872

Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies—that is, a centrally planned routing that minimizes the average cost of agents—is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem. Copyright © 2024, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：