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

Space-Efficient Parameterized algorithms on Graphs of Low Shrubdepth 31

学校读者我要写书评

暂无评论

Space-Efficient Parameterized Algorithms on Graphs of Low Sh...

31st Annual European Symposium on algorithms, ESA 2023

作者： Bergougnoux, Benjamin Chekan, Vera Ganian, Robert Kanté, Mamadou Moustapha Mnich, Matthias Oum, Sang-Il Pilipczuk, Michal van Leeuwen, Erik Jan Institute of Informatics University of Warsaw Poland Humboldt-Universität zu Berlin Germany Algorithms and Complexity Group TU Wien Austria Université Clermont Auvergne Clermont Auvergne INP LIMOS CNRS Clermont-Ferrand France Hamburg University of Technology Institute for Algorithms and Complexity Germany Daejeon Korea Republic of Department of Mathematical Sciences KAIST Daejeon Korea Republic of Dept. Information and Computing Sciences Utrecht University Netherlands

ISBN: (纸本)9783959772952

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, Independent Set can be solved in time 2O(dk) · nO(1) using O(dk2 log n) space;Max Cut can be solved in time nO(dk) using O(dk log n) space;and Dominating Set can be solved in time 2O(dk) · nO(1) using nO(1) space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial. © Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthia

关键词： Dynamic programming

Single machine batch scheduling to minimize the weighted number of tardy Jobs

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Hermelin, Danny Mnich, Matthias Omlor, Simon Ben-Gurion University of the Negev Beer-Sheva Tu Hamburg Institute for Algorithms and Complexity Hamburg

The 1|B,rj| wjUjscheduling problem takes as input a batch setup time Δ and a set of n jobs, each having a processing time, a release date, a weight, and a due date;the task is to find a sequence of batches that minimizes the weighted number of tardy jobs. This problem was introduced by Hochbaum and Landy in 1994;as a wide generalization of r Knapsack, it is NP-hard. In this work we provide a multivariate complexity analysis of the 1|B, rj| wjUjproblem with respect to several natural parameters. That is, we establish a thorough classifica-tion into fixed-parameter tractable and Wr1s-hard problems, for parameter combinations of (i) #p = distinct number of processing times, (ii) #w = number of distinct weights, (iii) #d = number of distinct due dates, (iv) #r = number of distinct release dates, and (v) b = batch sizes. Thereby, we significantly extend the work of Hermelin et al. (2018) who analyzed the parameterized complexity of the non-batch variant of this problem without r release dates. As one of our key results, we prove that 1|B,rj| wjUjis Wr1s-hard parameterized by the number of distinct processing times and distinct due dates. To the best of our r knowledge, these are the first parameterized intractability results for scheduling problems with few distinct processing times. Further, we show that 1|B, rj| wjUjis fixed-parameter tractable with respect to parameter #p#d#r and with respect to parameter #w#d if there is just a single release date. Both results hold even if the number of jobs per batch is limited by some integer b. Copyright © 2019, The Authors. All rights reserved.

关键词： Parameterization

Exact bounds for distributed graph colouring 1

学校读者我要写书评

暂无评论

22nd International Colloquium on Structural Information and Communication complexity, SIROCCO 2015

作者： Rybicki, Joel Suomela, Jukka Helsinki Institute for Information Technology HIIT Department of Computer Science Aalto University Saarbrücken Finland Department of Algorithms and Complexity Max Planck Institute for Informatics Saarbrücken Germany

ISBN: (数字)9783319252582

ISBN: (纸本)9783319252575

We prove exact bounds on the time complexity of distributed graph colouring. If we are given a directed path that is properly coloured with n colours, by prior work it is known that we can find a proper 3-colouring (Formula presented.)in communication rounds. We close the gap between upper and lower bounds: we show that for infinitely many n the time complexity is precisely (Formula presented.) communication rounds. © Springer International Publishing Switzerland 2015.

关键词： Graph theory

Resource and service discovery for large-scale robot networks in disaster scenarios

学校读者我要写书评

暂无评论

Resource and service discovery for large-scale robot network...

2005 IEEE International Workshop on Safety, Security and Rescue Robotics

作者： Du, Jia Lei Rührup, Stefan Witkowski, Ulf Rückert, Ulrich System and Circuit Technology Research Group Heinz Nixdorf Institute University of Paderborn 33102 Paderborn Germany Algorithms and Complexity Research Group Heinz Nixdorf Institute University of Paderborn 33102 Paderborn Germany

ISBN: (纸本)078038945X

If robots are deployed in large numbers in disaster scenarios, the ability to discover and exchange resources and services with other robots in an open, heterogeneous, large-scale network will be essential for a successful operation. In this paper we present a discovery protocol that enables robots to efficiently locate resources and services available in large-scale networks. It is specifically designed for robot networks which are characterized by potentially highly dynamic network topologies and high service announcement-to-lookup ratios. The protocol exploits the position data of the robots to increase scalability and efficiency. A cell-based overlay structure is created, with master nodes in each cell. Through proactive intra-cell communication and reactive inter-cell communication, scalability is ensured and the effects of node movements on the overall network are minimized. © 2005 IEEE.

关键词： Robotics

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

A Survey on Graph Problems Parameterized Above and Below Guaranteed Values

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Gutin, Gregory Mnich, Matthias Royal Holloway University of London Department of Computer Science Egham United Kingdom Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany

We survey the field of algorithms and complexity for graph problems parameterized above or below guaranteed values. Those problems seek, for a given graph G, a solution whose value is at least g(G) + k or at most g(G) − k, where g(G) is a guarantee on the value that any solution on G takes. The goal is to design algorithms which find such solution in time whose complexity in k is decoupled from that in the guarantee, or to rule out the existence of such algorithms by means of intractability results. We discuss a large number of algorithms and intractability results, and complement them by several open problems. Copyright © 2022, The Authors. All rights reserved.

关键词： Parameterization

Circumference of essentially 4-connected planar triangulations

学校读者我要写书评

暂无评论

Journal of Graph algorithms and Applications 2021年第1期25卷 121-132页

作者： Fabrici, Igor Harant, Jochen Mohr, Samuel Schmidt, Jens M. Institute of Mathematics P.J. Šafárik University in Košice Slovakia Institute of Mathematics Ilmenau University of Technology Germany Hamburg University of Technology Institute for Algorithms and Complexity Germany

A 3-connected graph G is essentially 4-connected if, for any 3-cut S ⊆ V (G) of G, at most one component of G − S contains at least two vertices. We prove that every essentially 4-connected maximal planar graph G on n... 详细信息

关键词： Triangulation

No Polynomial Kernels for Knapsack

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Heeger, Klaus Hermelin, Danny Mnich, Matthias Shabtay, Dvir Department of Industrial Engineering and Management Ben-Gurion University of the Negev Beer-Sheva Israel Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany

This paper focuses on kernelization algorithms for the fundamental Knapsack problem. A kernelization algorithm (or kernel) is a polynomial-time reduction from a problem onto itself, where the output size is bounded by a function of some problem-specific parameter. Such algorithms provide a theoretical model for data reduction and preprocessing and are central in the area of parameterized complexity. In this way, a kernel for Knapsack for some parameter k reduces any instance of Knapsack to an equivalent instance of size at most f(k) in polynomial time, for some computable function f(·). When f(k) = kO(1) then we call such a reduction a polynomial kernel. Our study focuses on two natural parameters for Knapsack: The number of different item weights w#, and the number of different item profits p#. Our main technical contribution is a proof showing that Knapsack does not admit a polynomial kernel for any of these two parameters under standard complexity-theoretic assumptions. Our proof discovers an elaborate application of the standard kernelization lower bound framework, and develops along the way novel ideas that should be useful for other problems as well. We complement our lower bounds by showing the Knapsack admits a polynomial kernel for the combined parameter w# + p# Copyright © 2023, The Authors. All rights reserved.

关键词： Profitability

A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Armbruster, Susanne Mnich, Matthias Nägele, Martin Research Institute for Discrete Mathematics Hausdorff Center for Mathematics University of Bonn Bonn Germany Hamburg University of Technology Institute for Algorithms and Complexity Germany

We present a new (3/2+1/e)-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classical metric Traveling Salesperson Problem (TSP) where a specified subset of vertices needs to appear on the output Hamiltonian cycle in a given order, and the task is to compute a cheapest such cycle. Our approximation guarantee of approximately 1.868 holds with respect to the value of a natural new linear programming (LP) relaxation for Ordered TSP. Our result significantly improves upon the previously best known guarantee of 5/2 for this problem and thereby considerably reduces the gap between approximability of Ordered TSP and metric TSP. Our algorithm is based on a decomposition of the LP solution into weighted trees that serve as building blocks in our tour construction. Copyright © 2024, The Authors. All rights reserved.

关键词： Approximation algorithms