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

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

来源：评论

学校读者我要写书评

暂无评论

Searching for Smallest Universal Graphs and Tournaments with SAT 29

Searching for Smallest Universal Graphs and Tournaments with...

引用

29th International Conference on Principles and Practice of Constraint Programming, CP 2023

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

ISBN: (纸本)9783959773003

A graph is induced k-universal if it contains all graphs of order k as an induced subgraph. For over half a century, the question of determining smallest k-universal graphs has been studied. A related question asks for a smallest k-universal tournament containing all tournaments of order k. This paper proposes and compares SAT-based methods for answering these questions exactly for small values of k. Our methods scale to values for which a generate-and-test approach isn't feasible;for instance, we show that an induced 7-universal graph has more than 16 vertices, whereas the number of all connected graphs on 16 vertices, modulo isomorphism, is a number with 23 decimal digits Our methods include static and dynamic symmetry breaking and lazy encodings, employing external subgraph isomorphism testing. © Tianwei Zhang and Stefan Szeider.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

Parameterized complexity of Efficient Sortation

arXiv

引用

arXiv 2024年

作者： Ganian, Robert Hoang, Hung P. Wietheger, Simon TU Vienna Algorithms and Complexity Group Austria

A crucial challenge arising in the design of large-scale logistical networks is to optimize parcel sortation for routing. We study this problem under the recent graph-theoretic formalization of Van Dyk, Klause, Koenemann and Megow (IPCO 2024). The problem asks-given an input digraph D (the fulfillment network) together with a set of commodities represented as source-sink tuples-for a minimum-outdegree subgraph H of the transitive closure of D that contains a source-sink route for each of the commodities. Given the underlying motivation, we study two variants of the problem which differ in whether the routes for the commodities are assumed to be given, or can be chosen arbitrarily. We perform a thorough parameterized analysis of the complexity of both problems. Our results concentrate on three fundamental parameterizations of the problem: 1. When attempting to parameterize by the target outdegree of H, we show that the problems are paraNP-hard even in highly restricted cases;2. When parameterizing by the number of commodities, we utilize Ramsey-type arguments and color-coding techniques to obtain parameterized algorithms for both problems;3. When parameterizing by the structure of D, we establish fixed-parameter tractability for both problems w.r.t. treewidth, maximum degree and the maximum routing length. We combine this with lower bounds which show that omitting any of the three parameters results in paraNPhardness. © 2024, CC BY.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Minimizing Switches in Cased Graph Drawings 32

Minimizing Switches in Cased Graph Drawings

引用

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

作者： Ganian, Robert Nöllenburg, Martin Röder, Sebastian Algorithms and Complexity Group TU Wien Austria TU Wien Austria

ISBN: (纸本)9783959773430

In cased drawings of graphs, edges are drawn in front of others in order to decrease the negative impact of crossings on readability. In this context, a switch on an edge is defined as two consecutive crossings, where the edge is drawn in the front at one crossing and behind another edge at the next crossing. We investigate the problem of minimizing the maximum number of switches on any edge - both in a fixed drawing as well as for non-embedded graphs. We resolve an open question by Eppstein, van Kreveld, Mumford, and Speckmann (2009) by establishing the NP-hardness of minimizing the number of switches in a fixed drawing, provide a fixed-parameter algorithm for this problem, and obtain a full characterization of the problem for non-embedded graphs. © Robert Ganian, Martin Nöllenburg, and Sebastian Röder.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Separating Incremental and Non-Incremental Bottom-Up Compilation 26

Separating Incremental and Non-Incremental Bottom-Up Compila...

引用

26th International Conference on Theory and Applications of Satisfiability Testing, SAT 2023

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

ISBN: (纸本)9783959772860

The aim of a compiler is, given a function represented in some language, to generate an equivalent representation in a target language L. In bottom-up (BU) compilation of functions given as CNF formulas, constructing the new representation requires compiling several subformulas in L. The compiler starts by compiling the clauses in L and iteratively constructs representations for new subformulas using an "Apply" operator that performs conjunction in L, until all clauses are combined into one representation. In principle, BU compilation can generate representations for any subformulas and conjoin them in any way. But an attractive strategy from a practical point of view is to augment one main representation - which we call the core - by conjoining to it the clauses one at a time. We refer to this strategy as incremental BU compilation. We prove that, for known relevant languages L for BU compilation, there is a class of CNF formulas that admit BU compilations to L that generate only polynomial-size intermediate representations, while their incremental BU compilations all generate an exponential-size core. © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Program compilers

来源：评论

学校读者我要写书评

暂无评论

Proven Optimally-Balanced Latin Rectangles with SAT 29

Proven Optimally-Balanced Latin Rectangles with SAT

引用

29th International Conference on Principles and Practice of Constraint Programming, CP 2023

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

ISBN: (纸本)9783959773003

Motivated by applications from agronomic field experiments, Díaz, Le Bras, and Gomes [CPAIOR 2015] introduced Partially Balanced Latin Rectangles as a generalization of Spatially Balanced Latin Squares. They observed that the generation of Latin rectangles that are optimally balanced is a highly challenging computational problem. They computed, utilizing CSP and MIP encodings, Latin rectangles up to 12 × 12, some optimally balanced, some suboptimally balanced. In this paper, we develop a SAT encoding for generating balanced Latin rectangles. We compare experimentally encoding variants. Our results indicate that SAT encodings perform competitively with the MIP encoding, in some cases better. In some cases we could find Latin rectangles that are more balanced than previously known ones. This finding is significant, as there are many arithmetic constraints involved. The SAT approach offers the advantage that we can certify that Latin rectangles are optimally balanced through DRAT proofs that can be verified independently. © Vaidyanathan Peruvemba Ramaswamy and Stefan Szeider.

关键词： Encoding (symbols)

来源：评论

学校读者我要写书评

暂无评论

Constrained Boundary Labeling 35

Constrained Boundary Labeling

引用

35th International Symposium on algorithms and Computation, ISAAC 2024

作者： Depian, Thomas Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Algorithms and Complexity Group TU Wien Austria Algorithms cluster TU Eindhoven Netherlands Technical University of Munich Germany

ISBN: (纸本)9783959773546

Boundary labeling is a technique in computational geometry used to label dense sets of feature points in an illustration. It involves placing labels along an axis-aligned bounding box and connecting each label with its corresponding feature point using non-crossing leader lines. Although boundary labeling is well-studied, semantic constraints on the labels have not been investigated thoroughly. In this paper, we introduce grouping and ordering constraints in boundary labeling: Grouping constraints enforce that all labels in a group are placed consecutively on the boundary, and ordering constraints enforce a partial order over the labels. We show that it is NP-hard to find a labeling for arbitrarily sized labels with unrestricted positions along one side of the boundary. However, we obtain polynomial-time algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Finally, we show that finding a labeling on two opposite sides of the boundary is NP-complete, even for uniform-height labels and finite label positions. © Thomas Depian, Martin Nöllenburg, Soeren Terziadis, and Markus Wallinger.

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

A (3/2 + Ε)-Approximation for Multiple TSP with a Variable Number of Depots 31

A (3/2 + Ε)-Approximation for Multiple TSP with a Variable ...

引用

31st Annual European Symposium on algorithms, ESA 2023

作者： Deppert, Max Kaul, Matthias Mnich, Matthias Institute for Algorithms and Complexity Hamburg University of Technology Germany

ISBN: (纸本)9783959772952

One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the Multiple TSP: a set of m ≥ 1 salespersons collectively traverses a set of n cities by m non-trivial tours, to minimize the total length of their tours. This problem can also be considered to be a variant of Uncapacitated Vehicle Routing, where the objective is to minimize the sum of all tour lengths. When all m tours start from and end at a single common depot v0, then the metric Multiple TSP can be approximated equally well as the standard metric TSP, as shown by Frieze (1983). The metric Multiple TSP becomes significantly harder to approximate when there is a set D of d ≥ 1 depots that form the starting and end points of the m tours. For this case, only a (2 − 1/d)-approximation in polynomial time is known, as well as a 3/2-approximation for constant d which requires a prohibitive run time of nΘ(d) (Xu and Rodrigues, INFORMS J. Comput., 2015). A recent work of Traub, Vygen and Zenklusen (STOC 2020) gives another approximation algorithm for metric Multiple TSP with run time nΘ(d), which reduces the problem to approximating metric TSP. In this paper we overcome the nΘ(d) time barrier: we give the first efficient approximation algorithm for Multiple TSP with a variable number d of depots that yields a better-than-2 approximation. Our algorithm runs in time (1/Ε)O(d log d) · nO(1), and produces a (3/2 + Ε)-approximation with constant probability. For the graphic case, we obtain a deterministic 3/2-approximation in time 2d · nO(1) © Max Deppert, Matthias Kaul, and Matthias Mnich.

关键词： Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：