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

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)

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines 34

New Support Size Bounds for Integer Programming, Applied to ...

引用

34th International Symposium on algorithms and Computation, ISAAC 2023

作者： Berndt, Sebastian Brinkop, Hauke Jansen, Klaus Mnich, Matthias Stamm, Tobias Institute for Theoretical Computer Science University of Lübeck Germany Kiel University Germany Hamburg University of Technology Institute for Algorithms and Complexity Germany

ISBN: (纸本)9783959772891

Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows that any feasible integer linear program (ILP) has a solution with support size s ≤ 2m · log(4m∆), where m is the number of constraints, and ∆ is the largest absolute coefficient in any constraint. Our main combinatorial result are improved support size bounds for ILPs. We show that any ILP has a solution with support size s ≤ m · (log(3Amax) + plog(Amax)), where Amax:= A1 denotes the 1-norm of the constraint matrix A. Furthermore, we show support bounds in the linearized form s ≤ 2m · log(1.46Amax). Our upper bounds also hold with Amax replaced by √m∆, which improves on the previously best constants in the linearized form. Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. We design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||Cmax). Our EPTAS yields a (1 + Ε)-approximation for Q||Cmax on N jobs in time 2O(1/Ε log3(1/Ε) log(log(1/Ε))) + O(N), which improves over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020) with run time 2O(1/Ε log4(1/Ε)) + NO(1) . Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation which greatly benefits from the small support. © Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich, and Tobias Stamm;licensed under Creative Commons License CC-BY 4.0.

关键词： Integer programming

来源：评论

学校读者我要写书评

暂无评论

No Polynomial Kernels for Knapsack 51

No Polynomial Kernels for Knapsack

引用

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

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

ISBN: (纸本)9783959773225

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 w# of different item weights, and the number p# of different item profits. 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 that Knapsack admits a polynomial kernel for the combined parameter w# · p#. © Klaus Heeger, Danny Hermelin, Matthias Mnich, and Dvir Shabtay.

关键词： Profitability

来源：评论

学校读者我要写书评

暂无评论

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

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

引用

27th International Conference on Approximation algorithms for Combinatorial Optimization Problems, APPROX 2024 and the 28th International Conference on Randomization and Computation, RANDOM 2024

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

ISBN: (纸本)9783959773485

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 classic 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. © Susanne Armbruster, Matthias Mnich, and Martin Nägele.

关键词： Hamiltonians

来源：评论

学校读者我要写书评

暂无评论

HITTING WEIGHTED EVEN CYCLES IN PLANAR GRAPHS

HITTING WEIGHTED EVEN CYCLES IN PLANAR GRAPHS

引用

作者： Goke, Alexander Koenemann, Jochen Mnich, Matthias Sun, Hao Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Department of Combinatorics & Optimization University of Waterloo WaterlooONN2L 3G1 Canada

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 Ƒ. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTASs) for planar input graphs G, using a variety of techniques like the shifting technique [B. S. Baker, J. ACM, 41 (1994), pp. 153-180], bidimensionality [F. V. Fomin et al., Bidimensionality and EPTAS, in Proceedings of SODA 2011, ACM, New York, SIAM, Philadelphia, 2011, pp. 748-759], or connectivity domination [V. Cohen-Addad et al., Approximating connectivity domination in weighted bounded-genus graphs, in Proceedings of STOC 2016, ACM, New York, 2016, pp. 584-597]. 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, Joret, and Pietropaoli [Hitting diamonds and growing cacti, in Proceedings of IPCO 2010, Lecture Notes in Comput. Sci. 6080, Springer, Berlin, 2010, pp. 191-204] 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 upper bound of the same value for the standard LP relaxation on node-weighted planar graphs. © 2022 Alexander Göke, Jochen Koenemann, Matthias Mnich, Hao Sun.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：