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

The complexity of Optimizing Atomic Congestion

学校读者我要写书评

暂无评论

arXiv 2023年

作者： 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

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 © 2023, The Authors. All rights reserved.

关键词： Separators

A SAT Attack on Rota’s Basis Conjecture 25

学校读者我要写书评

暂无评论

A SAT Attack on Rota’s Basis Conjecture

25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022

作者： Kirchweger, Markus Scheucher, Manfred Szeider, Stefan Algorithms and Complexity Group TU Wien Austria Institut für Mathematik Technische Universität Berlin Germany

ISBN: (纸本)9783959772426

The SAT modulo Symmetries (SMS) is a recently introduced framework for dynamic symmetry breaking in SAT instances. It combines a CDCL SAT solver with an external lexicographic minimality checking algorithm. We extend SMS from graphs to matroids and use it to progress on Rota’s Basis Conjecture (1989), which states that one can always decompose a collection of r disjoint bases of a rank r matroid into r disjoint rainbow bases. Through SMS, we establish that the conjecture holds for all matroids of rank 4 and certain special cases of matroids of rank 5. Furthermore, we extend SMS with the facility to produce DRAT proofs. External tools can then be used to verify the validity of additional axioms produced by the lexicographic minimality check. As a byproduct, we have utilized our framework to enumerate matroids modulo isomorphism and to support the investigation of various other problems on matroids. © Markus Kirchweger, Manfred Scheucher, and Stefan Szeider.

关键词： Combinatorial mathematics

Layered Area-Proportional Rectangle Contact Representations 29th

学校读者我要写书评

暂无评论

Layered Area-Proportional Rectangle Contact Representations

29th International Symposium on Graph Drawing and Network Visualization, GD 2021

作者： Nöllenburg, Martin Villedieu, Anaïs Wulms, Jules Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030929305

We investigate two optimization problems on area-proportional rectangle contact representations for layered, embedded planar graphs. The vertices are represented as interior-disjoint unit-height rectangles of prescribed widths, grouped in one row per layer, and each edge is ideally realized as a rectangle contact of positive length. Such rectangle contact representations find applications in semantic word or tag cloud visualizations, where a collection of words is displayed such that pairs of semantically related words are close to each other. In this paper, we want to maximize the number of realized rectangle contacts or minimize the overall area of the rectangle contact representation, while avoiding any false adjacencies. We present a network flow model for area minimization, a linear-time algorithm for contact maximization of two-layer graphs, and an ILP model for maximizing contacts of k-layer graphs. © 2021, Springer Nature Switzerland AG.

关键词： Semantics

Boundary Labeling in a Circular Orbit

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bonerath, Annika Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Wulms, Jules University of Bonn Germany Algorithms and Complexity Group TU Wien Austria TU Eindhoven Netherlands

Boundary labeling is a well-known method for displaying short textual labels for a set of point features in a figure alongside the boundary of that figure. Labels and their corresponding points are connected via crossing-free leaders. We propose orbital boundary labeling as a new variant of the problem, in which (i) the figure is enclosed by a circular contour and (ii) the labels are placed as disjoint circular arcs in an annulus-shaped orbit around the contour. The algorithmic objective is to compute an orbital boundary labeling with the minimum total leader length. We identify several parameters that define the corresponding problem space: two leader types (straight or orbital-radial), label size and order, presence of candidate label positions, and constraints on where a leader attaches to its label. Our results provide polynomial-time algorithms for many variants and NP-hardness for others, using a variety of geometric and combinatorial insights. © 2024, CC BY.

关键词： Polynomial approximation

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

学校读者我要写书评

暂无评论

Hedonic Diversity Games: A Complexity Picture with More than...

36th AAAI Conference on Artificial Intelligence, AAAI 2022

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

ISBN: (纸本)1577358767

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 complete 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 posed in previous work. © 2022, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： Color

New complexity-theoretic frontiers of tractability for neural network training 23

学校读者我要写书评

暂无评论

New complexity-theoretic frontiers of tractability for neura...

Proceedings of the 37th International Conference on Neural Information Processing Systems

作者： Cornelius Brand Robert Ganian Mathis Rocton Algorithms & Complexity Group Vienna University of Technology Vienna Austria

In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, less progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art. In particular, for ReLU networks we establish the polynomial-time tractability of all architectures where hidden neurons have an out-degree of 1, improving upon the previous algorithm of Arora, Basu, Mianjy and Mukherjee. On the other hand, for networks with linear activation functions we identify the first non-trivial polynomial-time solvable class of networks by obtaining an algorithm that can optimally train network architectures satisfying a novel data throughput condition.

关键词：

Parameterized complexity of Caching in Networks 39

学校读者我要写书评

暂无评论

Parameterized Complexity of Caching in Networks

39th Annual AAAI Conference on Artificial Intelligence, AAAI 2025

作者： Ganian, Robert Inerney, Fionn Mc Tsigkari, Dimitra Algorithms and Complexity Group TU Wien Vienna Austria Telefónica Scientific Research Barcelona Spain

ISBN: (纸本)157735897X

The fundamental caching problem in networks asks to find an allocation of contents to a network of caches with the aim of maximizing the cache hit rate. Despite the problem's importance to a variety of research areas-including not only content delivery, but also edge intelligence and inference-and the extensive body of work on empirical aspects of caching, very little is known about the exact boundaries of tractability for the problem beyond its general NP-hardness. We close this gap by performing a comprehensive complexity-theoretic analysis of the problem through the lens of the parameterized complexity paradigm, which is designed to provide more precise statements regarding algorithmic tractability than classical complexity. Our results include algorithmic lower and upper bounds which together establish the conditions under which the caching problem becomes tractable. Copyright © 2025, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： NP-hard

Fixed-Parameter algorithms for Computing RAC Drawings of Graphs

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Brand, Cornelius Ganian, Robert Röder, Sebastian Schager, Florian Algorithms and Complexity Group TU Wien Vienna University of Technology Austria

In a right-angle crossing (RAC) drawing of a graph, each edge is represented as a polyline and edge crossings must occur at an angle of exactly 90◦, where the number of bends on such polylines is typically restricted in some way. While structural and topological properties of RAC drawings have been the focus of extensive research, little was known about the boundaries of tractability for computing such drawings. In this paper, we initiate the study of RAC drawings from the viewpoint of parameterized complexity. In particular, we establish that computing a RAC drawing of an input graph G with at most b bends (or determining that none exists) is fixed-parameter tractable parameterized by either the feedback edge number of G, or b plus the vertex cover number of G. © 2023, CC BY.

关键词： Parameter estimation

Parameterized complexity of Caching in Networks*

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ganian, Robert Inerney, Fionn Mc Tsigkari, Dimitra Algorithms and Complexity Group TU Wien Vienna Austria Telefónica Scientific Research Barcelona Spain

The fundamental caching problem in networks asks to find an allocation of contents to a network of caches with the aim of maximizing the cache hit rate. Despite the problem's importance to a variety of research areas-including not only content delivery, but also edge intelligence and inference-and the extensive body of work on empirical aspects of caching, very little is known about the exact boundaries of tractability for the problem beyond its general NPhardness. We close this gap by performing a comprehensive complexity-theoretic analysis of the problem through the lens of the parameterized complexity paradigm, which is designed to provide more precise statements regarding algorithmic tractability than classical complexity. Our results include algorithmic lower and upper bounds which together establish the conditions under which the caching problem becomes tractable. Copyright © 2024, The Authors. All rights reserved.

关键词： Complex networks