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

arXiv 2022年

作者： Dobler, Alexander Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

Linear diagrams are an effective way to visualize set-based data by representing elements as columns and sets as rows with one or more horizontal line segments, whose vertical overlaps with other rows indicate set intersections and their contained elements. The efficacy of linear diagrams heavily depends on having few line segments. The underlying minimization problem has already been explored heuristically, but its computational complexity has yet to be classified. In this paper, we show that minimizing line segments in linear diagrams is equivalent to a well-studied NP-hard problem, and extend the NP-hardness to a restricted setting. We develop new algorithms for computing linear diagrams with minimum number of line segments that build on a traveling salesperson (TSP) formulation and allow constraints on the element orders, namely, forcing two sets to be drawn as single line segments, giving weights to sets, and allowing hierarchical constraints via PQ-trees. We conduct an experimental evaluation and compare previous algorithms for minimizing line segments with our TSP formulation, showing that a state-of-the art TSP-solver can solve all considered instances optimally, most of them within few milliseconds. © 2022, CC BY.

关键词： Optimization

来源：评论

学校读者我要写书评

暂无评论

Hedonic Diversity Games: A complexity Picture with More than Two Colors

arXiv

引用

arXiv 2022年

作者： Ganian, Robert Hamm, Thekla Knop, Dušan Schierreich, Šimon Suchý, Ondřej Algorithms and Complexity Group TU Wien Austria Algorithms and Complexity Group Utrecht University Netherlands Faculty of Information Technology Czech Technical University Prague Czech Republic

Hedonic diversity games are a variant of the classical hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the model) and provided some initial complexity-theoretic and existential results concerning Nash and individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a comprehensive parameterized-complexity picture for computing Nash and individually stable outcomes with respect to the most natural parameterizations of the problem. Crucially, our results hold for general hedonic diversity games where the number of colors is not necessarily restricted to two, and show that—apart from two trivial cases—a necessary condition for tractability in this setting is that the number of colors is bounded by the parameter. Moreover, for the special case of two colors we resolve an open question asked in previous work (Boehmer and Elkind, AAAI 2020). Copyright © 2022, The Authors. All rights reserved.

关键词： Color

来源：评论

学校读者我要写书评

暂无评论

Longest Cycle above Erdos-Gallai Bound 30

Longest Cycle above Erdos-Gallai Bound

引用

30th Annual European Symposium on algorithms, ESA 2022

作者： Fomin, Fedor V. Golovach, Petr A. Sagunov, Danil Simonov, Kirill Department of Informatics University of Bergen Norway St. Petersburg Department V.A. Steklov Institute of Mathematics Russia Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772471

In 1959, Erdos and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2O(k) nO(1) decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G) + k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

The Fine-Grained complexity of Graph Homomorphism Parameterized by Clique-Width 49

The Fine-Grained Complexity of Graph Homomorphism Parameteri...

引用

49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022

作者： Ganian, Robert Hamm, Thekla Korchemna, Viktoriia Okrasa, Karolina Simonov, Kirill Algorithms and Complexity Group TU Wien Austria Faculty of Matematics and Information Science Warsaw University of Technology Poland Faculty of Mathematics Informatics and Mechanics University of Warsaw Poland

ISBN: (纸本)9783959772358

The generic homomorphism problem, which asks whether an input graph G admits a homomorphism into a fixed target graph H, has been widely studied in the literature. In this article, we provide a fine-grained complexity classification of the running time of the homomorphism problem with respect to the clique-width of G (denoted cw) for virtually all choices of H under the Strong Exponential Time Hypothesis. In particular, we identify a property of H called the signature number s(H) and show that for each H, the homomorphism problem can be solved in time O∗(s(H)cw). Crucially, we then show that this algorithm can be used to obtain essentially tight upper bounds. Specifically, we provide a reduction that yields matching lower bounds for each H that is either a projective core or a graph admitting a factorization with additional properties - allowing us to cover all possible target graphs under long-standing conjectures. © Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, and Kirill Simonov;licensed under Creative Commons License CC-BY 4.0

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

A Parameterized Theory of PAC Learning

arXiv

引用

arXiv 2023年

作者： Brand, Cornelius Ganian, Robert Simonov, Kirill Algorithms and Complexity Group TU Wien Austria Chair for Algorithm Engineering Hasso Plattner Institute Germany

Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the class P in classical computational complexity. But while the nascent theory of parameterized complexity has allowed us to push beyond the P-NP "dichotomy" in classical computational complexity and identify the exact boundaries of tractability for numerous problems, there is no analogue in the domain of sample complexity that could push beyond efficient PAC learnability. As our core contribution, we fill this gap by developing a theory of parameterized PAC learning which allows us to shed new light on several recent PAC learning results that incorporated elements of parameterized complexity. Within the theory, we identify not one but two notions of fixed-parameter learnability that both form distinct counterparts to the class FPT—the core concept at the center of the parameterized complexity paradigm—and develop the machinery required to exclude fixed-parameter learnability. We then showcase the applications of this theory to identify refined boundaries of tractability for CNF and DNF learning as well as for a range of learning problems on graphs. © 2023, CC BY.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem 18

From Data Completion to Problems on Hypercubes: A Parameteri...

引用

18th International Symposium on Parameterized and Exact Computation, IPEC 2023

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Ordyniak, Sebastian Szeider, Stefan Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Austria School of Computing DePaul University ChicagoIL United States School of Computing University of Leeds United Kingdom

ISBN: (纸本)9783959773058

Several works have recently investigated the parameterized complexity of data completion problems, motivated by their applications in machine learning, and clustering in particular. Interestingly, these problems can be equivalently formulated as classical graph problems on induced subgraphs of powers of partially-defined hypercubes. In this paper, we follow up on this recent direction by investigating the Independent Set problem on this graph class, which has been studied in the data science setting under the name Diversity. We obtain a comprehensive picture of the problem's parameterized complexity and establish its fixed-parameter tractability w.r.t. the solution size plus the power of the hypercube. Given that several such FO-definable problems have been shown to be fixed-parameter tractable on the considered graph class, one may ask whether fixed-parameter tractability could be extended to capture all FO-definable problems. We answer this question in the negative by showing that FO model checking on induced subgraphs of hypercubes is as difficult as FO model checking on general graphs. © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Model checking

来源：评论

学校读者我要写书评

暂无评论

Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized algorithms 47

Long Cycles in Graphs: Extremal Combinatorics Meets Paramete...

引用

47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022

ISBN: (纸本)9783959772563

We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d > 1, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdos-Gallai from 1959, states that a graph G with the average vertex degree D > 1, contains a cycle of length at least D. The proofs of these theorems are constructive, they provide polynomial-time algorithms constructing cycles of lengths 2d and D. We extend these algorithmic results by showing that each of the problems, to decide whether a 2-connected graph contains a cycle of length at least 2d + k or of a cycle of length at least D + k, is fixed-parameter tractable parameterized by k. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Minimum Link Fencing 33

Minimum Link Fencing

引用

33rd International Symposium on algorithms and Computation, ISAAC 2022

作者： Bhore, Sujoy Klute, Fabian Löffler, Maarten Nöllenburg, Martin Terziadis, Soeren Villedieu, Anaïs Department of Computer Science & Engineering Indian Institute of Technology Bombay India Department of Information and Computing Sciences Utrecht University Netherlands Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772587

We study a variant of the geometric multicut problem, where we are given a set P of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where P contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of P \ {Q} does not intersect Q. © Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu.

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for Clustered Planarity with Linear Saturators 35

Exact Algorithms for Clustered Planarity with Linear Saturat...

引用

35th International Symposium on algorithms and Computation, ISAAC 2024

作者： Da Lozzo, Giordano Ganian, Robert Gupta, Siddharth Mohar, Bojan Ordyniak, Sebastian Zehavi, Meirav Roma Tre University Italy Algorithms and Complexity Group TU Wien Austria BITS Pilani K K Birla Goa Campus India Department of Mathematics Simon Fraser University Burnaby Canada University of Leeds United Kingdom Ben-Gurion University of the Negev Beer-Sheva Israel

ISBN: (纸本)9783959773546

We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an n-vertex planar graph whose vertices are partitioned into independent sets (called clusters) with paths - one for each cluster - that connect all the vertices in each cluster while maintaining planarity. We show that the problem can be solved in time 2O(n) for both the variable and fixed embedding case. Moreover, we show that it can be solved in subexponential time 2O(√n log n) in the fixed embedding case if additionally the input graph is connected. The latter time complexity is tight under the Exponential-Time Hypothesis. We also show that n can be replaced with the vertex cover number of the input graph by providing a linear (resp. polynomial) kernel for the variable-embedding (resp. fixed-embedding) case;these results contrast the NP-hardness of the problem on graphs of bounded treewidth (and even on trees). Finally, we complement known lower bounds for the problem by showing that Clustered Planarity with Linear Saturators is NP-hard even when the number of clusters is at most 3, thus excluding the algorithmic use of the number of clusters as a parameter. © Giordano Da Lozzo, Robert Ganian, Siddharth Gupta, Bojan Mohar, Sebastian Ordyniak, and Meirav Zehavi.

关键词： Graph embeddings

来源：评论

学校读者我要写书评

暂无评论

Near-Tight Runtime Guarantees for Many-Objective Evolutionary algorithms

arXiv

引用

arXiv 2024年

作者： Wietheger, Simon Doerr, Benjamin Algorithms and Complexity Group Technische Universität Wien Vienna Austria CNRS École Polytechnique Institut Polytechnique de Paris Palaiseau France

Despite significant progress in the field of mathematical runtime analysis of multi-objective evolutionary algorithms (MOEAs), the performance of MOEAs on discrete many-objective problems is little understood. In particular, the few existing bounds for the SEMO, global SEMO, and SMS-EMOA algorithms on classic benchmarks are all roughly quadratic in the size of the Pareto front. In this work, we prove near-tight runtime guarantees for these three algorithms on the four most common benchmark problems OneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros, and OneJumpZeroJump, and this for arbitrary numbers of objectives. Our bounds depend only linearly on the Pareto front size, showing that these MOEAs on these benchmarks cope much better with many objectives than what previous works suggested. Our bounds are tight apart from small polynomial factors in the number of objectives and length of bitstrings. This is the first time that such tight bounds are proven for many-objective uses of these MOEAs. While it is known that such results cannot hold for the NSGA-II, we do show that our bounds, via a recent structural result, transfer to the NSGA-III algorithm. Copyright © 2024, The Authors. All rights reserved.

关键词： Evolutionary algorithms

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：