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

The complexity of Extending Fair Allocations of Indivisible Goods

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Deligkas, Argyrios Eiben, Eduard Ganian, Robert Goldsmith, Tiger-Lily Ioannidis, Stavros D. Department of Computer Science Royal Holloway University of London United Kingdom Algorithms and Complexity group TU Wien Austria

We initiate the study of computing envy-free allocations of indivisible items in the extension setting, i.e., when some part of the allocation is fixed and the task is to allocate the remaining items. Given the known NP-hardness of the problem, we investigate whether—and under which conditions—one can obtain fixed-parameter algorithms for computing a solution in settings where most of the allocation is already fixed. Our results provide a broad complexity-theoretic classification of the problem which includes: (a) fixed-parameter algorithms tailored to settings with few distinct types of agents or items;(b) lower bounds which exclude the generalization of these positive results to more general settings. We conclude by showing that—unlike when computing allocations from scratch—the non-algorithmic question of whether more relaxed EFX allocations exist can be completely resolved in the extension *** Codes 91B32 Copyright © 2025, The Authors. All rights reserved.

关键词：

The Parameterized complexity of Coordinated Motion Planning 39

学校读者我要写书评

暂无评论

The Parameterized Complexity of Coordinated Motion Planning

39th International Symposium on Computational Geometry, SoCG 2023

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad 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

ISBN: (纸本)9783959772730

In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the k robots to their destinations which minimizes a certain objective target - prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former objective target as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous (n2 − 1)-puzzle as a special case. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish - as a simpler case - the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids. © Eduard Eiben, Robert Ganian, and Iyad Kanj;licensed under Creative Commons License CC-BY 4.0.

关键词： Motion planning

Twin-Width Meets Feedback Edges and Vertex Integrity

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Balabán, Jakub Ganian, Robert Rocton, Mathis Faculty of Informatics Masaryk University Brno Czech Republic Algorithms and Complexity Group TU Wien Vienna Austria

The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towards obtaining a better understanding of this question is to consider the approximability of twin-width via fixed-parameter algorithms whose running time depends not on twin-width itself, but rather on parameters which impose stronger restrictions on the input graph. The first step that article made in this direction is to establish the fixed-parameter approximability of twin-width (with an additive error of 1) when the runtime parameter is the feedback edge number. Here, we make several new steps in this research direction and obtain: An asymptotically tight bound between twin-width and the feedback edge number;A significantly improved fixed-parameter approximation algorithm for twin-width under the same runtime parameter (i.e., the feedback edge number) which circumvents many of the technicalities of the original result and simultaneously avoids its formerly non-elementary runtime dependency;An entirely new fixed-parameter approximation algorithm for twin-width when the runtime parameter is the vertex integrity of the graph. © 2024, CC BY.

关键词： Approximation algorithms

SAT-Based Search for Minwise Independent Families

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Iurlano, Enrico Raidl, Günther R. Algorithms and Complexity Group TU Wien Favoritenstraße 9-11/192-01 Vienna1040 Austria

Proposed for rapid document similarity estimation in web search engines, the celebrated property of minwise independence imposes highly symmetric constraints on a family F of permutations of {1, ..., n}: The property is fulfilled by F if for each j ∈ {1, ..., n}, any cardinality-j subset X ⊆ {1, ..., n}, and any fixed element x∗ ∈ X, it occurs with probability 1/j that a randomly drawn permutation π from F satisfies π(x∗) = min{π(x): x ∈ X}. The central interest is to find a family with fewest possible members meeting the stated constraints. We provide a framework that, firstly, is realized as a pure SAT model and, secondly, generalizes a heuristic of Mathon and van Trung to the search of these families. Originally, the latter enforces an underlying group-theoretic decomposition to achieve a significant speed-up for the computer-aided search of structures which can be identified with so-called rankwise independent families. We observe that this approach is suitable to find provenly optimal new representatives of minwise independent families while yielding a decisive speed-up, too. As the problem has a naive search space of size at least (n!)n, we also carefully address symmetry breaking. Finally, we add a bijective proof for a problem encountered by Bargachev when deriving a lower bound on the number of members in a minimal rankwise independent *** Codes 90C27, 68R05 © 2024, CC BY-SA.

关键词： group theory

Problems on group-Labeled Matroid Bases 51

学校读者我要写书评

暂无评论

Problems on Group-Labeled Matroid Bases

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Hörsch, Florian Imolay, András Mizutani, Ryuhei Oki, Taihei Schwarcz, Tamás Algorithms and Complexity Group CISPA Saarbrücken Germany MTA-ELTE Matroid Optimization Research Group Department of Operations Research ELTE Eötvös Loránd University Budapest Hungary Department of Mathematical Informatics Graduate School of Information Science and Technology The University of Tokyo Japan

ISBN: (纸本)9783959773225

Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We study a collection of problems on finding bases and common bases of matroids with restrictions on their labels. For zero bases and zero common bases, the results are mostly negative. While finding a non-zero basis of a matroid is not difficult, it turns out that the complexity of finding a non-zero common basis depends on the group. Namely, we show that the problem is hard for a fixed group if it contains an element of order two, otherwise it is polynomially solvable. As a generalization of both zero and non-zero constraints, we further study F-avoiding constraints where we seek a basis or common basis whose label is not in a given set F of forbidden labels. Using algebraic techniques, we give a randomized algorithm for finding an F-avoiding common basis of two matroids represented over the same field for finite groups given as operation tables. The study of F-avoiding bases with groups given as oracles leads to a conjecture stating that whenever an F-avoiding basis exists, an F-avoiding basis can be obtained from an arbitrary basis by exchanging at most |F| elements. We prove the conjecture for the special cases when |F| ≤ 2 or the group is ordered. By relying on structural observations on matroids representable over fixed, finite fields, we verify a relaxed version of the conjecture for these matroids. As a consequence, we obtain a polynomial-time algorithm in these special cases for finding an F-avoiding basis when |F| is fixed. © Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz.

关键词： Polynomial approximation

The Parameterized complexity of Network Microaggregation 37

学校读者我要写书评

暂无评论

The Parameterized Complexity of Network Microaggregation

37th AAAI Conference on Artificial Intelligence, AAAI 2023

作者： Blažej, Václav Ganian, Robert Knop, Dušan Pokorný, Jan Schierreich, Šimon Simonov, Kirill Faculty of Information Technology Czech Technical University in Prague Prague Czech Republic Algorithms and Complexity Group Technische Universität Wien Vienna Austria Hasso Plattner Institute University of Potsdam Postdam Germany

ISBN: (纸本)9781577358800

Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network. Copyright © 2023, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： Parameterization

Parameterized algorithms for Coordinated Motion Planning: Minimizing Energy 51

学校读者我要写书评

暂无评论

Parameterized Algorithms for Coordinated Motion Planning: Mi...

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Deligkas, Argyrios Eiben, Eduard Ganian, Robert Kanj, Iyad Ramanujan, M.S. 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 Department of Computer Science University of Warwick Coventry United Kingdom

ISBN: (纸本)9783959773225

We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of k robots to their destinations with the aim of minimizing the total energy (i.e., the total length traveled). We develop novel techniques to push beyond previously-established results that were restricted to solid grids. We design a fixed-parameter additive approximation algorithm for this problem parameterized by k alone. This result, which is of independent interest, allows us to prove the following two results pertaining to well-studied coordinated motion planning problems: (1) A fixed-parameter algorithm, parameterized by k, for routing a single robot to its destination while avoiding the other robots, which is related to the famous Rush-Hour Puzzle;and (2) a fixed-parameter algorithm, parameterized by k plus the treewidth of the input graph, for the standard Coordinated Motion Planning (CMP) problem in which we need to route all the k robots to their destinations. The latter of these results implies, among others, the fixed-parameter tractability of CMP parameterized by k on graphs of bounded outerplanarity, which include bounded-height subgrids. We complement the above results with a lower bound which rules out the fixed-parameter tractability for CMP when parameterized by the total energy. This contrasts the recently-obtained tractability of the problem on solid grids under the same parameterization. As our final result, we strengthen the aforementioned fixed-parameter tractability to hold not only on solid grids but all graphs of bounded local treewidth – a class including, among others, all graphs of bounded genus. © Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan.

关键词： Parameterization

Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Brand, Cornelius Ceylan, Esra Ganian, Robert Hatschka, Christian Korchemna, Viktoriia Algorithms and Complexity Group TU Wien Vienna Austria

Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for NP-hard graph problems. For problems that are W[1]-hard parameterized by treewidth, a natural alternative would be to use a suitable analogue of treewidth that is based on edge cuts instead of vertex separators. While tree-cut width has been coined as such an analogue of treewidth for edge cuts, its algorithmic applications have often led to disappointing results: out of twelve problems where one would hope for fixed-parameter tractability parameterized by an edge-cut based analogue to treewidth, eight were shown to be W[1]-hard parameterized by tree-cut width. As our main contribution, we develop an edge-cut based analogue to treewidth called edge-cut width. Edge-cut width is, intuitively, based on measuring the density of cycles passing through a spanning tree of the graph. Its benefits include not only a comparatively simple definition, but mainly that it has interesting algorithmic properties: it can be computed by a fixed-parameter algorithm, and it yields fixed-parameter algorithms for all the aforementioned problems where tree-cut width failed to do so. © 2022, CC BY.

关键词： Parameterization

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chew, Leroy de Colnet, Alexis Slivovsky, Friedrich Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria Department of Computer Science University of Liverpool Liverpool United Kingdom

Parity reasoning is challenging for Conflict-Driven Clause Learning (CDCL) SAT solvers. This has been observed even for simple formulas encoding two contradictory parity constraints with different variable orders (Chew and Heule 2020). We provide an analytical explanation for their hardness by showing that they require exponential resolution refutations with high probability when the variable order is chosen at random. We obtain this result by proving that these formulas, which are known to be Tseitin formulas, have Tseitin graphs of linear treewidth with high probability. Since such Tseitin formulas require exponential resolution proofs, our result follows. We generalize this argument to a new class of formulas that capture a basic form of parity reasoning involving a sum of two random parity constraints with random orders. Even when the variable order for the sum is chosen favorably, these formulas remain hard for resolution. In contrast, we prove that they have short DRAT refutations. We show experimentally that the running time of CDCL SAT solvers on both classes of formulas grows exponentially with their treewidth. © 2024, CC BY.

关键词： Hardness