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

42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025

作者： Ghorbani, Ebrahim Hoff, Jonah Leander Mnich, Matthias Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany

ISBN: (纸本)9783959773652

Propp machines, or rotor-router models, are a classic tool to simulate random systems in forms of Markov chains by deterministic systems. To this end, the nodes of the Markov chain are replaced by switching nodes, which maintain a queue over their outgoing arcs, and a particle sent through the system traverses the top arc of the queue which is then moved to the end of the queue and the particle arrives at the next node. A key question to answer about such systems is whether a single particle can reach a particular target node, given as input an initial configuration of the queues at all switching nodes. This question was introduced by Dohrau et al. (2017) under the name of Arrival. A major open question is whether Arrival can be solved in polynomial time, as it is known to lie in NP ∩ co-NP;yet the fastest known algorithm for general instances takes subexponential time (Gärtner et al., ICALP 2021). We consider a generalized version of Arrival introduced by Auger et al. (RP 2023), which requires routing multiple (potentially exponentially many) particles through a rotor graph. The Multi-Arrival problem is to determine the particle configuration that results from moving all particles from a given initial configuration to sinks. Auger et al. showed that for path-like rotor graphs with a certain uniform rotor order, the problem can be solved in polynomial time. Our main result is a quasi-polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs for arbitrary rotor orders. Tree-like rotor graphs are directed multigraphs which can be obtained from undirected trees by replacing each edge by an arbitrary number of arcs in either or both directions. For trees of bounded contracted height, such as paths, the algorithm runs in polynomial time and thereby generalizes the result by Auger et al.. Moreover, we give a polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs without parallel arcs. © Ebrahim Ghorbani, Jonah Leander Hoff, and Matthias Mnich.

关键词： Chains

来源：评论

学校读者我要写书评

暂无评论

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously 42

Approximate Minimum Tree Cover in All Symmetric Monotone Nor...

引用

42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025

作者： Kaul, Matthias Luo, Kelin Mnich, Matthias Röglin, Heiko Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany University of Bonn Germany University at Buffalo NY United States Universität Bonn Germany

ISBN: (纸本)9783959773652

We study the problem of partitioning a set of n objects in a metric space into k clusters V1,..., Vk. The quality of the clustering is measured by considering the vector of cluster costs and then minimizing some monotone symmetric norm of that vector (in particular, this includes the p-norms). For the costs of the clusters we take the weight of a minimum-weight spanning tree on the objects in Vi, which may serve as a proxy for the cost of traversing all objects in the cluster, for example in the context of Multirobot Coverage as studied by Zheng, Koenig, Kempe, Jain (IROS 2005), but also as a shape-invariant measure of cluster density similar to Single-Linkage Clustering. This problem has been studied by Even, Garg, Könemann, Ravi, Sinha (Oper. Res. Lett., 2004) for the setting of minimizing the weight of the largest cluster (i.e., using ∞) as Min-Max Tree Cover, for which they gave a constant-factor approximation algorithm. We provide a careful adaptation of their algorithm to compute solutions which are approximately optimal with respect to all monotone symmetric norms simultaneously, and show how to find them in polynomial time. In fact, our algorithm is purely combinatorial and can process metric spaces with 10,000 points in less than a second. As an extension, we also consider the case where instead of a target number of clusters we are provided with a set of depots in the space such that every cluster should contain at least one such depot. One can consider these as the fixed starting points of some agents that will traverse all points of a cluster. For this setting also we are able to give a polynomial-time algorithm computing a constant-factor approximation with respect to all monotone symmetric norms simultaneously. To show that the algorithmic results are tight up to the precise constant of approximation attainable, we also prove that such clustering problems are already APX-hard when considering only one single p norm for the objective. © Matthias Kaul, K

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously

arXiv

引用

arXiv 2025年

作者： Kaul, Matthias Luo, Kelin Mnich, Matthias Röglin, Heiko Universität Bonn Bonn Germany University at Buffalo New York United States Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany

We study the problem of partitioning a set of n objects in a metric space into k clusters V1, . . ., Vk. The quality of the clustering is measured by considering the vector of cluster costs and then minimizing some monotone symmetric norm of that vector (in particular, this includes the p-norms). For the costs of the clusters we take the weight of a minimum-weight spanning tree on the objects in Vi, which may serve as a proxy for the cost of traversing all objects in the cluster, for example in the context of Multirobot Coverage as studied by Zheng, Koenig, Kempe, Jain (IROS 2005), but also as a shape-invariant measure of cluster density similar to Single-Linkage Clustering. This setting has been studied by Even, Garg, Könemann, Ravi, Sinha (Oper. Res. Lett., 2004) for the setting of minimizing the weight of the largest cluster (i.e., using ∞) as Min-Max Tree Cover, for which they gave a constant-factor approximation. We provide a careful adaptation of their algorithm to compute solutions which are approximately optimal with respect to all monotone symmetric norms simultaneously, and show how to find them in polynomial time. In fact, our algorithm is purely combinatorial and can process metric spaces with 10,000 points in less than a second. As an extension, we also consider the case where instead of a target number of clusters we are provided with a set of depots in the space such that every cluster should contain at least one such depot. One can consider these as the fixed starting points of some agents that will traverse all points of a cluster. For this setting also we are able to give a polynomial time algorithm computing a constant factor approximation with respect to all monotone symmetric norms simultaneously. To show that the algorithmic results are tight up to the precise constant of approximation attainable, we also prove that such clustering problems are already APX-hard when considering only one single p norm for the objective. © 2025, CC BY.

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Solving problems on graphs of high rank-width 14th

Solving problems on graphs of high rank-width

引用

14th International Symposium on algorithms and Data Structures, WADS 2015

作者： Eiben, Eduard Ganian, Robert Szeider, Stefan Algorithms and Complexity Group Institute of Computer Graphics and Algorithms TU Wien Vienna Austria

ISBN: (纸本)9783319218397

A modulator of a graph G to a specified graph class H is a set of vertices whose deletion puts G into H. The cardinality of a modulator to various graph classes has long been used as a structural parameter which can be exploited to obtain FPT algorithms for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width). Can such modulators still be exploited to obtain efficient algorithms? And is it even possible to find such modulators efficiently? We first show that the parameters derived from such well-structured modulators are strictly more general than the cardinality of modulators and rank-width itself. Then, we develop an FPT algorithm for finding such well-structured modulators to any graph class which can be characterized by a finite set of forbidden induced subgraphs. We proceed by showing how well-structured modulators can be used to obtain efficient parameterized algorithms for MINIMUM VERTEX COVER and MAXIMUM CLIQUE. Finally, we use the concept of well-structured modulators to develop an algorithmic meta-theorem for efficiently deciding problems expressible in Monadic Second Order (MSO) logic, and prove that this result is tight in the sense that it cannot be generalized to LinEMSO problems. © Springer International Publishing Switzerland 2015.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

A (3/2 + Ε)-Approximation for Multiple TSP with a Variable Number of Depots 31

A (3/2 + Ε)-Approximation for Multiple TSP with a Variable ...

引用

31st Annual European Symposium on algorithms, ESA 2023

作者： Deppert, Max Kaul, Matthias Mnich, Matthias Institute for Algorithms and Complexity Hamburg University of Technology Germany

ISBN: (纸本)9783959772952

One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the Multiple TSP: a set of m ≥ 1 salespersons collectively traverses a set of n cities by m non-trivial tours, to minimize the total length of their tours. This problem can also be considered to be a variant of Uncapacitated Vehicle Routing, where the objective is to minimize the sum of all tour lengths. When all m tours start from and end at a single common depot v0, then the metric Multiple TSP can be approximated equally well as the standard metric TSP, as shown by Frieze (1983). The metric Multiple TSP becomes significantly harder to approximate when there is a set D of d ≥ 1 depots that form the starting and end points of the m tours. For this case, only a (2 − 1/d)-approximation in polynomial time is known, as well as a 3/2-approximation for constant d which requires a prohibitive run time of nΘ(d) (Xu and Rodrigues, INFORMS J. Comput., 2015). A recent work of Traub, Vygen and Zenklusen (STOC 2020) gives another approximation algorithm for metric Multiple TSP with run time nΘ(d), which reduces the problem to approximating metric TSP. In this paper we overcome the nΘ(d) time barrier: we give the first efficient approximation algorithm for Multiple TSP with a variable number d of depots that yields a better-than-2 approximation. Our algorithm runs in time (1/Ε)O(d log d) · nO(1), and produces a (3/2 + Ε)-approximation with constant probability. For the graphic case, we obtain a deterministic 3/2-approximation in time 2d · nO(1) © Max Deppert, Matthias Kaul, and Matthias Mnich.

关键词： Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

Hitting weighted even cycles in planar graphs 24

Hitting weighted even cycles in planar graphs

引用

24th International Conference on Approximation algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021

作者： Göke, Alexander Koenemann, Jochen Mnich, Matthias Sun, Hao Hamburg University of Technology Institute for Algorithms and Complexity Germany University of Waterloo Canada

ISBN: (纸本)9783959772075

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family F. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTAS) for planar input graphs G, using a variety of techniques like the shifting technique (Baker, J. ACM 1994), bidimensionality (Fomin et al., SODA 2011), or connectivity domination (Cohen-Addad et al., STOC 2016). These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the even-cycle transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini et al. (IPCO 2010) showed that the integrality gap of the standard covering LP relaxation is Θ(log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7 ≈ 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap of the same value for the standard LP relaxation on node-weighted planar graphs. © Alexander Göke, Jochen Koenemann, Matthias Mnich, and Hao Sun;licensed under Creative Commons License CC-BY 4.0

关键词： Undirected graphs

来源：评论

学校读者我要写书评

暂无评论

Polynomial kernels for edge modification problems towards block and strictly chordal graphs

引用

Discrete Mathematics and Theoretical Computer Science 2025年 272卷

作者： Dumas, Maël Perez, Anthony Rocton, Mathis Todinca, Ioan Institute of Informatics University of Warsaw Warsaw Poland Université d’Orléans INSA CVL LIFO UR 4022 Orléans France Algorithms and Complexity Group TU Wien Vienna Austria

We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph G = (V, E) and an integer k ∈ N and seeks to edit (add or delete) at most k edges from G to obtain a block graph or a strictly chordal graph. The completion and deletion variants of these problems are defined similarly by only allowing edge additions for the former and only edge deletions for the latter. Block graphs are a well-studied class of graphs and admit several characterizations, e.g. they are diamond-free chordal graphs. Strictly chordal graphs, also referred to as block duplicate graphs, are a natural generalization of block graphs where one can add true twins of cut-vertices. Strictly chordal graphs are exactly dart and gem-free chordal graphs. We prove the NP-completeness for most variants of these problems and provide: © 2025 by the author(s)

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

A Relative Value Function Based Learning Beam Search for the Longest Common Subsequence Problem 18th

A Relative Value Function Based Learning Beam Search for th...

引用

18th International Conference on Computer Aided Systems Theory, EUROCAST 2022

作者： Huber, M. Raidl, G.R. Algorithms and Complexity Group Institute of Logic and Computation TU Wien Vienna Austria

ISBN: (纸本)9783031253119

Beam search (BS) is a well-known graph search algorithm frequently used to heuristically find good or near-optimal solutions to combinatorial optimization problems. Its most crucial component is a heuristic function that estimates the best achievable length-to-go from any state to a goal state. This function usually needs to be developed specificially for a problem at hand, which is a manual and time-consuming process. Building on previous work, we propose a Relative Value Function Based Learning Beam Search (RV-LBS) to automate this task at least partially by using a multilayer perceptron (MLP) as heuristic function, which is trained in a reinforcement learning manner on many randomly created problem instances. This MLP predicts the difference of the expected solution length from a given state to the expected average solution length of all states at a current BS level. To support the training of the MLP on the longest common subsequence (LCS) problem, a compact fixed-size encoding of the distribution of differences of remaining string lengths to the average string length at the current level is presented. Tests show that a MLP trained by RV-LBS on randomly created small-size problem instances is able to guide BS well also on larger established LCS benchmark instances. The obtained results are highly competitive to the state-of-the-art. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： Benchmarking

来源：评论

学校读者我要写书评

暂无评论

On Short Fastest Paths in Temporal Graphs 15th

On Short Fastest Paths in Temporal Graphs

引用

15th International Conference on algorithms and Computation, WALCOM 2021

作者： Danda, Umesh Sandeep Ramakrishna, G. Schmidt, Jens M. Srikanth, M. Indian Institute of Technology Tirupati Tirupati India Institute for Algorithms and Complexity TU Hamburg Hamburg Germany Hyderabad India

ISBN: (纸本)9783030682101

Temporal graphs equip their directed edges with a departure time and a duration, which allows to model a surprisingly high number of real-world problems. Recently, Wu et al. have shown that a fastest path in a temporal graph G from a given vertex s to a vertex z can be computed in near-linear time, where a fastest path is one that minimizes the arrival time at z minus the departure time at s. Here, we consider the natural problem of computing a fastest path from s to z that is in addition short, i.e. minimizes the sum of durations of its edges;this maximizes the total amount of spare time at stops during the journey. Using a new dominance relation on paths in combination with lexicographic orders on the departure and arrival times of these paths, we derive a near-linear time algorithm for this problem with running time O(n+ mlog p(G) ), where n: = | V(G) |, m: = | E(G) | and p(G) is upper bounded by both the maximum in-degree and the maximum edge duration of G. The dominance relation is interesting in its own right, and may be of use for several related problems like fastest paths with minimum fare, fastest paths with minimum number of stops, and other pareto-optimal path problems in temporal graphs. © 2021, Springer Nature Switzerland AG.

关键词： Clustering algorithms

来源：评论

学校读者我要写书评

暂无评论

Foundations of evolutionary multi-objective optimization 11

Foundations of evolutionary multi-objective optimization

引用

13th Annual Genetic and Evolutionary Computation Conference - Companion Publication, GECCO 2011 Companion

作者： Friedrich, Tobias Neumann, Frank Algorithms and Complexity Max Planck Institute for Informatics Germany School of Computer Science University of Adelaide Australia

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：