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

Parameterized algorithms for Queue Layouts

学校读者我要写书评

暂无评论

Journal of Graph algorithms and Applications 2022年第3期26卷 335-352页

作者： Bhore, Sujoy Ganian, Robert Montecchiani, Fabrizio Nöllenburg, Martin Bruxelles Belgium Algorithms and Complexity Group TU Wien Vienna Austria Engineering Department University of Perugia Perugia Italy

An h-queue layout of a graph G consists of a linear order of its vertices and a partition of its edges into h sets, called queues, such that no two independent edges of the same queue nest. The minimum h such that G admits an h-queue layout is the queue number of G. We present two fixed-parameter tractable algorithms that exploit structural properties of graphs to compute optimal queue layouts. As our first result, we show that deciding whether a graph G has queue number 1 and computing a corresponding layout is fixed-parameter tractable when parameterized by the treedepth of G. Our second result then uses a more restrictive parameter, the vertex cover number, to solve the problem for arbitrary h. © 2022, Brown University. All rights reserved.

关键词： Parameter estimation

MaxSAT-Based Postprocessing for Treedepth 26th

学校读者我要写书评

暂无评论

MaxSAT-Based Postprocessing for Treedepth

26th International Conference on Principles and Practice of Constraint Programming, CP 2020

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

ISBN: (纸本)9783030584740

Treedepth is an increasingly popular graph invariant. Many NP-hard combinatorial problems can be solved efficiently on graphs of bounded treedepth. Since the exact computation of treedepth is itself NP-hard, recent research has focused on the development of heuristics that compute good upper bounds on the treedepth. In this paper, we introduce a novel MaxSAT-based approach for improving a heuristically obtained treedepth decomposition. At the core of our approach is an efficient MaxSAT encoding of a weighted generalization of treedepth arising naturally due to subtree contractions. The encoding is applied locally to the given treedepth decomposition to reduce its depth, in conjunction with the collapsing of subtrees. We show the local improvement method’s correctness and provide an extensive experimental evaluation with some encouraging results. © 2020, Springer Nature Switzerland AG.

关键词： Forestry

Skipping the Crowds: Cognitive Impact of Real-Time On-Board Crowding Information in Mass Transit Smartphone Mobility Apps

学校读者我要写书评

暂无评论

SSRN

SSRN 2024年

作者： Prabhakar, Archana Grison, Elise Morgagni, Simone Nöllenburg, Martin Gyselinck, Valérie SNCF Research Department La Plaine Saint-Denis France Université Gustave Eiffel Université Paris Cité Versailles France Algorithms and Complexity Group TU Wien Vienna Austria

Dense mass transit systems are prone to suboptimal exploitation of their infrastructure when passenger congestion concentrates on specific routes, leaving alternative routes underused. This imbalance may arise from passengers relying on a cognitive heuristic to find the fastest path without considering other parameters, partly for lack of information. Providing on-board crowding information via smartphone mobility apps before boarding could increase their willingness-to-wait for a less crowded route. An online experimental paradigm was designed to investigate how individuals evaluate different combinations of crowding levels, waiting times, and in-vehicle times when selecting routes for non-time-sensitive trips in the Parisian mass transit which is unfamiliar to them. We aimed to simulate the dynamic nature of passengers' decision-making processes and provide insights into the cognitive mechanisms underlying real-world decisions. Results indicate that the participants showed greater willingness-to-wait for less crowded alternatives, especially when the default route was highly crowded, and the alternative route lightly crowded. Short waiting times and long in-vehicle times also increased willingness-to-wait. Thus, our findings confirm that the availability of crowding information in smartphone mobility apps during route planning can effectively regulate passenger flow in mass transit. This lever lowers passengers’ reliance on a cognitive heuristic to find the fastest route, guiding them towards less crowded alternatives. © 2024, The Authors. All rights reserved.

关键词： Travel time

Learning Depth Vision-Based Personalized Robot Navigation From Dynamic Demonstrations in Virtual Reality

学校读者我要写书评

暂无评论

arXiv 2022年

作者： de Heuvel, Jorge Corral, Nathan Kreis, Benedikt Conradi, Jacobus Driemel, Anne Bennewitz, Maren Group for Algorithms and Complexity University of Bonn Germany Lamarr Institute for Machine Learning and Artificial Intelligence Germany

— For the best human-robot interaction experience, the robot’s navigation policy should take into account personal preferences of the user. In this paper, we present a learning framework complemented by a perception pipeline to train a depth vision-based, personalized navigation controller from user demonstrations. Our virtual reality interface enables the demonstration of robot navigation trajectories under motion of the user for dynamic interaction scenarios. The novel perception pipeline enrolls a variational autoencoder in combination with a motion predictor. It compresses the perceived depth images to a latent state representation to enable efficient reasoning of the learning agent about the robot’s dynamic environment. In a detailed analysis and ablation study, we evaluate different configurations of the perception pipeline. To further quantify the navigation controller’s quality of personalization, we develop and apply a novel metric to measure preference reflection based on the Fréchet Distance. We discuss the robot’s navigation performance in various virtual scenes and demonstrate the first personalized robot navigation controller that solely relies on depth images. A supplemental video highlighting our approach is available online1 Copyright © 2022, The Authors. All rights reserved.

关键词： Demonstrations

A Structural complexity Analysis of Synchronous Dynamical Systems

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Korchemna, Viktoriia Department of Computer Science Royal Holloway University of London United Kingdom Algorithms and Complexity Group TU Wien Austria Eindhoven University of Technology Netherlands

Synchronous dynamic systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product adoption. We study the three most notable problems in synchronous dynamic systems: whether the system will transition to a target configuration from a starting configuration, whether the system will reach convergence from a starting configuration, and whether the system is guaranteed to converge from every possible starting configuration. While all three problems were known to be intractable in the classical sense, we initiate the study of their exact boundaries of tractability from the perspective of structural parameters of the network by making use of the more fine-grained parameterized complexity paradigm. As our first result, we consider treewidth—as the most prominent and ubiquitous structural parameter—and show that all three problems remain intractable even on instances of constant treewidth. We complement this negative finding with fixed-parameter algorithms for the former two problems parameterized by treedepth, a well-studied restriction of treewidth. While it is possible to rule out a similar algorithm for convergence guarantee under treedepth, we conclude with a fixed-parameter algorithm for this last problem when parameterized by treedepth and the maximum in-degree. © 2023, CC BY.

关键词： Parameterization

ALGORITHMIC APPLICATIONS OF TREE-CUT WIDTH

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Ganian, Robert Kim, Eun Jung Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria CNRS Université Paris-Dauphine Paris France

The recently introduced graph parameter tree-cut width plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. In this paper, we provide the first algorithmic applications of tree-cut width to hard combinatorial problems. Tree-cut width is known to be lower-bounded by a function of treewidth, but it can be much larger and hence has the potential to facilitate the efficient solution of problems that are not known to be fixed-parameter tractable (FPT) when parameterized by treewidth. We introduce the notion of nice tree-cut decompositions and provide FPT algorithms for the showcase problems Capacitated Vertex Cover, Capacitated Dominating Set, and Imbalance parameterized by the tree-cut width of an input graph. On the other hand, we show that List Coloring, Precoloring Extension, and Boolean CSP (the latter parameterized by the tree-cut width of the incidence graph) are W[1]-hard and hence unlikely to be fixed-parameter tractable when parameterized by tree-cut width. Copyright © 2022, The Authors. All rights reserved.

关键词： Integer programming

Fully Dynamic Maximum Independent Sets of Disks in Polylogarithmic Update Time 40

学校读者我要写书评

暂无评论

Fully Dynamic Maximum Independent Sets of Disks in Polylogar...

40th International Symposium on Computational Geometry, SoCG 2024

作者： Bhore, Sujoy Nöllenburg, Martin Tóth, Csaba D. Wulms, Jules Department of Computer Science and Engineering Indian Institute of Technology Bombay Mumbai India Institute of Logic and Computation Algorithms and Complexity Group TU Wien Austria Department of Mathematics California State University Northridge Los AngelesCA United States Department of Computer Science Tufts University MedfordMA United States Department of Mathematics and Computer Science TU Eindhoven Netherlands

ISBN: (纸本)9783959773164

A fundamental question is whether one can maintain a maximum independent set (MIS) in polylogarithmic update time for a dynamic collection of geometric objects in Euclidean space. For a set of intervals, it is known that no dynamic algorithm can maintain an exact MIS in sublinear update time. Therefore, the typical objective is to explore the trade-off between update time and solution size. Substantial efforts have been made in recent years to understand this question for various families of geometric objects, such as intervals, hypercubes, hyperrectangles, and fat objects. We present the first fully dynamic approximation algorithm for disks of arbitrary radii in the plane that maintains a constant-factor approximate MIS in polylogarithmic expected amortized update time. Moreover, for a fully dynamic set of n unit disks in the plane, we show that a 12-approximate MIS can be maintained with worst-case update time O(log n), and optimal output-sensitive reporting. This result generalizes to fat objects of comparable sizes in any fixed dimension d, where the approximation ratio depends on the dimension and the fatness parameter. Further, we note that, even for a dynamic set of disks of unit radius in the plane, it is impossible to maintain O(1 + Ε)-approximate MIS in truly sublinear update time, under standard complexity assumptions. Our results build on two recent technical tools: (i) The MIX algorithm by Cardinal et al. (ESA 2021) that can smoothly transition from one independent set to another;hence it suffices to maintain a family of independent sets where the largest one is an O(1)-approximate MIS. (ii) A dynamic nearest/farthest neighbor data structure for disks by Kaplan et al. (DCG 2020) and Liu (SICOMP 2022), which generalizes the dynamic convex hull data structure by Chan (JACM 2010), and quickly yields a "replacement" disk (if any) when a disk in one of our independent sets is deleted. © Sujoy Bhore, Martin Nöllenburg, Csaba D. Tóth, and Jules Wulms.

关键词： Data structures

Parameterised Partially-Predrawn Crossing Number

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Hamm, Thekla Hliněný, Petr Algorithms and Complexity Group TU Wien Vienna Austria Faculty of Informatics Masaryk University Brno Czech Republic

Inspired by the increasingly popular research on extending partial graph drawings, we propose a new perspective on the traditional and arguably most important geometric graph parameter, the crossing number. Specifically, we define the partially predrawn crossing number to be the smallest number of crossings in any drawing of a graph, part of which is prescribed on the input (not counting the prescribed crossings). Our main result - an FPT-algorithm to compute the partially predrawn crossing number - combines advanced ideas from research on the classical crossing number and so called partial planarity in a very natural but intricate way. Not only do our techniques generalise the known FPT-algorithm by Grohe for computing the standard crossing number, they also allow us to substantially improve a number of recent parameterised results for various drawing extension *** Codes 68R10, 68U05 Copyright © 2022, The Authors. All rights reserved.

关键词： Parameterization

Counting Vanishing Matrix-Vector Products

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Brand, Cornelius Korchemna, Viktoriia Skotnica, Michael Simonov, Kirill Algorithms and Complexity Group TU Wien Austria Department of Applied Mathematics Charles University Prague Czech Republic Hasso Plattner Institute University of Potsdam Germany

Consider the following parameterized counting variation of the classic subset sum problem, which arises notably in the context of higher homotopy groups of topological spaces: Let v ∈ Qd be a rational vector, (T1, T2 . . . Tm) a list of d × d rational matrices, S ∈ Qh×d a rational matrix not necessarily square and k a parameter. The goal is to compute the number of ways one can choose k matrices Ti1 , Ti2 , . . ., Tik from the list such that STik · · · Ti1 v = 0 ∈ Qh. In this paper, we show that this problem is #W[2]-hard for parameter k. As a consequence, computing the k-th homotopy group of a d-dimensional 1-connected topological space for d > 3 is #W[2]-hard for parameter k. We also discuss a decision version of the problem and its several modifications for which we show W[1]/W[2]-hardness. This is in contrast to the parameterized k-sum problem, which is only W[1]-hard (Abboud-Lewi-Williams, ESA’14). In addition, we show that the decision version of the problem without parameter is an undecidable problem, and we give a fixed-parameter tractable algorithm for matrices of bounded size over finite fields, parameterized the matrix dimensions and the order of the field. Copyright © 2023, The Authors. All rights reserved.

关键词： Matrix algebra