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

Selecting Matchings via Multiwinner Voting: How Structure Defeats a Large Candidate Space

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Boehmer, Niclas Brill, Markus Schmidt-Kraepelin, Ulrike Research Group Algorithmics and Computational Complexity TU Berlin Germany Research Group Efficient Algorithms TU Berlin Germany

Given a set of agents with approval preferences over each other, we study the task of finding k matchings fairly representing everyone’s preferences. We model the problem as an approval-based multiwinner election where the set of candidates consists of matchings of the agents, and agents’ preferences over each other are lifted to preferences over matchings. Due to the exponential number of candidates in such elections, standard algorithms for classical sequential voting rules (such as those proposed by Thiele and Phragmén) are rendered inefficient. We show that the computational tractability of these rules can be regained by exploiting the structure of the approval preferences. Moreover, we establish algorithmic results and axiomatic guarantees that go beyond those obtainable in the general multiwinner setting. Assuming that approvals are symmetric, we show that Proportional Approval Voting (PAV), a well-established but computationally intractable voting rule, becomes polynomial-time computable, and its sequential variant (seq-PAV), which does not provide any proportionality guarantees in general, fulfills a rather strong guarantee known as extended justified representation. Some of our algorithmic results extend to other types of compactly representable elections with an exponential candidate space. Copyright © 2021, The Authors. All rights reserved.

关键词： Polynomial approximation

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

Parameterized algorithms for the matrix completion problem

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Ganian, Robert Kanj, Iyad Ordyniak, Sebastian Szeider, Stefan Algorithms and Complexity Group TU Wien Austria School of Computing DePaul University Chicago United States

We consider two matrix completion problems, in which we are given a matrix with missing entries and the task is to complete the matrix in a way that (1) minimizes the rank, or (2) minimizes the number of distinct rows. We study the parameterized complexity of the two aforementioned problems with respect to several parameters of interest, including the minimum number of matrix rows, columns, and rows plus columns needed to cover all missing entries. We obtain new algorithmic results showing that, for the bounded domain case, both problems are fixed-parameter tractable with respect to all aforementioned parameters. We complement these results with a lower-bound result for the unbounded domain case that rules out fixed-parameter tractability w.r.t. some of the parameters under consideration. Copyright © 2018, The Authors. All rights reserved.

关键词： Matrix algebra

On strict (outer-)confluent graphs

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Förster, Henry Ganian, Robert Klute, Fabian Nöllenburg, Martin University of Tübingen Tübingen Germany Algorithms and Complexity Group TU Wien Vienna Austria

A strict confluent (SC) graph drawing is a drawing of a graph with vertices as points in the plane, where vertex adjacencies are represented not by individual curves but rather by unique smooth paths through a planar system of junctions and arcs. If all vertices of the graph lie in the outer face of the drawing, the drawing is called a strict outerconfluent (SOC) drawing. SC and SOC graphs were first considered by Eppstein et al. in Graph Drawing 2013. Here, we establish several new relationships between the class of SC graphs and other graph classes, in particular string graphs and unit-interval graphs. Further, we extend earlier results about special bipartite graph classes to the notion of strict outerconfluency, show that SOC graphs have cop number two, and establish that tree-like (∆-)SOC graphs have bounded cliquewidth. Copyright © 2019, The Authors. All rights reserved.

关键词： Drawing (graphics)

Parameterized algorithms for book embedding problems

学校读者我要写书评

暂无评论

arXiv 2019年

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

A k-page book embedding of a graph G draws the vertices of G on a line and the edges on k half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether G admits a k-page book embedding both when the linear order of the vertices is fixed, called Fixed-Order Book Thickness, or not fixed, called Book Thickness. Both problems are known to be NP-complete in general. We show that Fixed-Order Book Thickness and Book Thickness are fixed-parameter tractable parameterized by the vertex cover number of the graph and that Fixed-Order Book Thickness is fixed-parameter tractable parameterized by the pathwidth of the vertex order. Copyright © 2019, The Authors. All rights reserved.

关键词： Parameterization

A Tight Subexponential-time Algorithm for Two-Page Book Embedding

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ganian, Robert Müller, Haiko Ordyniak, Sebastian Paesani, Giacomo Rychlicki, Mateusz Algorithms and Complexity Group TU Wien Vienna Austria School of Computing University of Leeds United Kingdom

A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into "pages", which are half-planes bounded by that line. Two-page book embeddings, i.e., book embeddings into 2 pages, are of special importance as they are both NP-hard to compute and have specific applications. We obtain a 2O(√n) algorithm for computing a book embedding of an n-vertex graph on two pages—a result which is asymptotically tight under the Exponential Time Hypothesis. As a key tool in our approach, we obtain a single-exponential fixed-parameter algorithm for the same problem when parameterized by the treewidth of the input graph. We conclude by establishing the fixed-parameter tractability of computing minimum-page book embeddings when parameterized by the feedback edge number, settling an open question arising from previous work on the problem. Copyright © 2024, The Authors. All rights reserved.

关键词： Parameter estimation

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

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

A Parameterized Theory of PAC Learning

学校读者我要写书评

暂无评论

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