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

作者： 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

来源：评论

学校读者我要写书评

暂无评论

Bioinspired Computation in Combinatorial Optimization 1

引用

丛书名： Natural Computing Series

1000年

作者： Frank Neumann Carsten Witt

来源：评论

学校读者我要写书评

暂无评论

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates 19

Single-Machine Scheduling to Minimize the Number of Tardy Jo...

引用

19th International Symposium on Parameterized and Exact Computation, IPEC 2024

作者： Kaul, Matthias Mnich, Matthias Molter, Hendrik Universität Bonn Bonn Germany Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Department of Computer Science Ben-Gurion University of the Negev Beer-Sheva Israel

ISBN: (纸本)9783959773539

We study the fundamental scheduling problem 1 | rj | P wjUj: schedule a set of n jobs with weights, processing times, release dates, and due dates on a single machine, such that each job starts after its release date and we maximize the weighted number of jobs that complete execution before their due date. Problem 1 | rj | P wjUj generalizes both Knapsack and Partition, and the simplified setting without release dates was studied by Hermelin et al. [Annals of Operations Research, 2021] from a parameterized complexity viewpoint. Our main contribution is a thorough complexity analysis of 1 | rj | P wjUj in terms of four key problem parameters: the number p# of processing times, the number w# of weights, the number d# of due dates, and the number r# of release dates of the jobs. 1 | rj | P wjUj is known to be weakly para-NP-hard even if w# + d# + r# is constant, and Heeger and Hermelin [ESA, 2024] recently showed (weak) W[1]-hardness parameterized by p# or w# even if r# is constant. Algorithmically, we show that 1 | rj | P wjUj is fixed-parameter tractable parameterized by p# combined with any two of the remaining three parameters w#, d#, and r#. We further provide pseudo-polynomial XP-time algorithms for parameter r# and d#. To complement these algorithms, we show that 1 | rj | P wjUj is (strongly) W[1]-hard when parameterized by d# + r# even if w# is constant. Our results provide a nearly complete picture of the complexity of 1 | rj | P wjUj for p#, w#, d#, and r# as parameters, and extend those of Hermelin et al. [Annals of Operations Research, 2021] for the problem 1 || P wjUj without release dates. © Matthias Kaul, Matthias Mnich, and Hendrik Molter.

关键词： Job shop scheduling

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for Generalizations of Directed Feedback Vertex Set∗

arXiv

引用

arXiv 2020年

作者： Göke, Alexander Marx, Dániel Mnich, Matthias TU Hamburg Institute for Algorithms and Complexity Hamburg Germany Max-Planck-Institut für Informatik Saarbrücken Germany TU Hamburg Institute for Algorithms and Complexity Hamburg Germany

The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp’s 21 NP-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. [STOC 2008, J. ACM 2008] showed its fixed-parameter tractability via a 4kk!nO(1)-time algorithm, where k = |S|. Here we show fixed-parameter tractability of two generalizations of DFVS: • Find a smallest vertex set S such that every strong component of G − S has size at most s: we give an algorithm solving this problem in time 4k(ks + k + s)! · nO(1). This generalizes an algorithm by Xiao [JCSS 2017] for the undirected version of the problem. • Find a smallest vertex set S such that every non-trivial strong component of G − S is 1-out-regular: we give an algorithm solving this problem in time 2O(k3) · nO(1). We also solve the corresponding arc versions of these problems by fixed-parameter algorithms. Copyright © 2020, The Authors. All rights reserved.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

Self-stabilising byzantine clock synchronisation is almost as easy as consensus

arXiv

引用

arXiv 2017年

作者： Lenzen, Christoph Rybicki, Joel Department of Algorithms and Complexity Max Planck Institute for Informatics Saarland Informatics Campus

We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the n nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to f Copyright © 2017, The Authors. All rights reserved.

关键词： Stabilization

来源：评论

学校读者我要写书评

暂无评论

Untangling Circular Drawings: algorithms and complexity 32

Untangling Circular Drawings: Algorithms and Complexity

引用

32nd International Symposium on algorithms and Computation, ISAAC 2021

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Rutter, Ignaz Wu, Hsiang-Yun Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Austria Universität Passau Germany Research Unit of Computer Graphics TU Wien Austria

ISBN: (纸本)9783959772143

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G = (V, E) into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift◦(δG) as the minimum number of vertices that need to be shifted to resolve all crossings of δG. We show that the problem Circular Untangling, asking whether shift◦(δG) ≤ K for a given integer K, is NP-complete. Based on this result we study Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. In this case we provide a tight upper bound shift◦(δG) ≤ ⌊n2 ⌋ - 1, where n is the number of vertices in G, and present a polynomial-time algorithm to compute the circular shifting number of almost-planar drawings. © Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, and Hsiang-Yun Wu.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs 39

Polynomial-Time Approximation Schemes for Independent Packin...

引用

39th International Symposium on Computational Geometry, SoCG 2023

作者： Galby, Esther Munaro, Andrea Yang, Shizhou Institute for Algorithms and Complexity Technische Universität Hamburg Germany Department of Mathematical Physical and Computer Sciences University of Parma Italy School of Mathematics and Physics Queen's University Belfast United Kingdom

ISBN: (纸本)9783959772730

We investigate a relaxation of the notion of treewidth-fragility, namely tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graph classes. Our approach unifies and extends several known polynomial-time approximation schemes on seemingly unrelated graph classes, such as classes of intersection graphs of fat objects in a fixed dimension or proper minor-closed classes. We also study the related notion of layered tree-independence number, a relaxation of layered treewidth. © Esther Galby, Andrea Munaro, and Shizhou Yang;licensed under Creative Commons License CC-BY 4.0.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Multiplicative approximations and the hypervolume indicator

Multiplicative approximations and the hypervolume indicator

引用

11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

作者： Friedrich, Tobias Horoba, Christian Neumann, Frank Algorithms Group International Computer Science Institute Berkeley CA United States Fakultät für Informatik LS 2 Technische Universität Dortmund Dortmund Germany Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarbrücken Germany

ISBN: (纸本)9781605583259

Indicator-based algorithms have become a very popular approach to solve multi-objective optimization problems. In this paper, we contribute to the theoretical understanding of algorithms maximizing the hypervolume for a given problem by distributing μ points on the Pareto front. We examine this common approach with respect to the achieved multiplicative approximation ratio for a given multi-objective problem and relate it to a set of μ points on the Pareto front that achieves the best possible approximation ratio. For the class of linear fronts and a class of concave fronts, we prove that the hypervolume gives the best possible approximation ratio. In addition, we examine Pareto fronts of different shapes by numerical calculations and show that the approximation computed by the hypervolume may differ from the optimal approximation ratio. Copyright 2009 ACM.

关键词： Multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

Coloring random graphs online without creating monochromatic subgraphs

Coloring random graphs online without creating monochromatic...

引用

作者： Mütze, Torsten Rast, Thomas Spöhel, Reto Institute of Theoretical Computer Science ETH Zürich 8092 Zürich Switzerland Algorithms and Complexity Group Max-Planck-Institut für Informatik 66123 Saarbrücken Germany

ISBN: (纸本)9780898719932

Consider the following generalized notion of graph coloring: a coloring of the vertices of a graph G is valid w.r.t. some given graph F if there is no copy of F in G whose vertices all receive the same color. We study the problem of computing valid colorings of the binomial random graph Gn,p on n vertices with edge probability p = p(n) in the following online setting: the vertices of an initially hidden instance of Gn,p are revealed one by one (together with all edges leading to previously revealed vertices) and have to be colored immediately and irrevocably with one of r available colors. It is known that for any fixed graph F and any fixed integer r ≥ 2 this problem has a threshold p0(F,r,n) in the following sense: For any function p(n) = o(p0) there is a strategy that a.a.s. (asymptotically almost surely, i.e., with probability tending to 1 as n tends to infinity) finds an r-coloring of Gn,p that is valid w.r.t. F online, and for any function p(n) = ω(p0) any online strategy will a.a.s. fail to do so. In this work we establish a general correspondence between this probabilistic problem and a deterministic two-player game in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. This characterization allows us to compute, for any F and r, a value γ = γ(F,r) such that the threshold of the probabilistic problem is given by p0(F,r,n) = nγ. Our approach yields polynomial-time coloring algorithms that a.a.s. find valid colorings of Gn,p online in the entire regime below the respective thresholds, i.e., for any p(n) = o(n-γ).

关键词： Coloring

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：