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

Recent advances in practical data reduction

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Abu-Khzam, Faisal Lamm, Sebastian Mnich, Matthias Noe, Alexander Schulz, Christian Strash, Darren Lebanese American University Lebanon Karlsruhe Institute of Technologie Germany Hamburg University of Technology Institute for Algorithms and Complexity Germany University of Vienna Austria Heidelberg University Germany

Over the last two decades, significant advances have been made in the design and analysis of fixed-parameter algorithms for a wide variety of graph-theoretic problems. This has resulted in an algorithmic toolbox that is by now well-established. However, these theoretical algorithmic ideas have received very little attention from the practical perspective. We survey recent trends in data reduction engineering results for selected problems. Moreover, we describe concrete techniques that may be useful for future implementations in the area and give open problems and research questions. Copyright © 2020, The Authors. All rights reserved.

关键词： Data reduction

A Unifying Framework for Characterizing and Computing Width Measures 13

学校读者我要写书评

暂无评论

A Unifying Framework for Characterizing and Computing Width ...

13th Innovations in Theoretical Computer Science Conference, ITCS 2022

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Jaffke, Lars Kwon, O-Joung Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Austria Department of Informatics University of Bergen Norway Department of Mathematics Incheon National University Korea Republic of Discrete Mathematics Group Institute for Basic Science Daejeon Korea Republic of

ISBN: (纸本)9783959772174

algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify F-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of F-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can approximate every possible F-branchwidth, providing a unifying parameterized framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width decompositions. © Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, and O-joung Kwon;licensed under Creative Commons License CC-BY 4.0

关键词： Parameter estimation

Evolutionary algorithms and dynamic programming

学校读者我要写书评

暂无评论

Evolutionary algorithms and dynamic programming

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

作者： Doerr, Benjamin Eremeev, Anton Horoba, Christian Neumann, Frank Theile, Madeleine Algorithms and Complexity Max-Planck-Institut für Informatik Saarbrücken Germany Omsk Branch of Sobolev Institute of Mathematics Omsk Russia Fakultät für Informatik LS 2 TU Dortmund Dortmund Germany Institut für Mathematik TU Berlin Berlin Germany

ISBN: (纸本)9781605583259

Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation, which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how to develop evolutionary algorithms that have the additional ability of carrying out dynamic programming steps. Copyright 2009 ACM.

关键词： Dynamic programming

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

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

学校读者我要写书评

暂无评论

arXiv 2023年

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

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 coefficient in any constraint. Our main combinatorial result are improved support size bounds for ILPs. To improve granularity, we analyze for the largest 1-norm Amax of any column of the constraint matrix, instead of ∆. We show a support size upper bound of s ≤ m · (log(3Amax) + √log(Amax)), by deriving a new bound on the -1 branch of the Lambert W function. Additionally, we provide a lower bound of mlog(Amax), proving our result asymptotically optimal. Furthermore, we give support bounds of the form s ≤ 2m · log(1.46Amax). These improve upon the previously best constants by Aliev. et. al. (SIAM J. Optim. 2018), because all our upper bounds hold equally with Amax replaced by √m∆. Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. First, 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. Second, we consider Q|HM|Cma

关键词： Integer programming

External labeling techniques: A taxonomy and survey

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Bekos, Michael A. Niedermann, Benjamin Nöllenburg, Martin Institute for Informatics University of Tübingen Tübingen Germany Institute of Geodesy and Geoinformation University of Bonn Bonn Germany Algorithms and Complexity Group Tu Wien Vienna Austria

External labeling is frequently used for annotating features in graphical displays and visualizations, such as technical illustrations, anatomical drawings, or maps, with textual information. Such a labeling connects features within an illustration by thin leader lines with their labels, which are placed in the empty space surrounding the image. Over the last twenty years, a large body of literature in diverse areas of computer science has been published that investigates many different aspects, models, and algorithms for automatically placing external labels for a given set of features. This state-of-the-art report introduces a first unified taxonomy for categorizing the different results in the literature and then presents a comprehensive survey of the state of the art, a sketch of the most relevant algorithmic techniques for external labeling algorithms, as well as a list of open research challenges in this multidisciplinary research field. Copyright © 2019, The Authors. All rights reserved.

关键词： Taxonomies

Circumference of essentially 4-connected planar triangulations

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Fabrici, Igor Harant, Jochen Mohr, Samuel Schmidt, Jens M. Institute of Mathematics P.J. Šafárik University Košice Slovakia Institute of Mathematics Ilmenau University of Technology Germany Institute for Algorithms and Complexity Hamburg University of Technology 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 vertices contains a cycle of length at least 32 (n + 4);moreover, this bound is *** Codes 05C38, 05C10 Copyright © 2021, The Authors. All rights reserved.

关键词： Graph theory

Unit disk representations of embedded trees, outerplanar and multi-legged graphs

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bhore, Sujoy Löffler, Maarten Nickel, Soeren Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Department of Computing and Information Sciences Utrecht University Algorithms and Complexity Group TU Wien Vienna Austria

A unit disk intersection representation (UDR) of a graph G represents each vertex of G as a unit disk in the plane, such that two disks intersect if and only if their vertices are adjacent in G. A UDR with interior-disjoint disks is called a unit disk contact representation (UDC). We prove that it is NP-hard to decide if an outerplanar graph or an embedded tree admits a UDR. We further provide a linear-time decidable characterization of caterpillar graphs that admit a UDR. Finally we show that it can be decided in linear time if a lobster graph admits a weak UDC, which permits intersections between disks of non-adjacent vertices. © 2021, CC BY.

关键词： Trees (mathematics)

Dense steiner problems: Approximation algorithms and inapproximability

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Karpinski, Marek Lewandowski, Mateusz Meesum, Syed Mohammad Mnich, Matthias Universität Bonn Institut für Informatik Bonn Germany University of Wrocaw Institute of Computer Science Wrocaw Poland Tu Hamburg Institute for Algorithms and Complexity Hamburg Germany

The Steiner Tree problem is a classical problem in com-binatorial optimization: the goal is to connect a set T of terminals in a graph G by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the δ-dense version of Steiner Tree, where each terminal has at least δ|V(G) \ T| neighbours outside T, for a fixed δ > 0. They gave a PTAS for this problem. We study a generalization of pairwise δ-dense Steiner Forest, which asks for a minimum-size forest in G in which the nodes in each terminal set T1,... ,Tkare connected, and every terminal in Tihas at least δ|Tj| neighbours in Tj, and at least δ|S| nodes in S = V(G) \ (T1∪ · · · ∪ Tk), for each i,j in {1,... , k} with i ≠ j. Our first result is a polynomial-time approximation scheme for all δ > 1/2. Then, we show a (13/12 + ϵ)-approximation algorithm for δ = 1/2 and any ϵ > 0. We also consider the δ-dense Group Steiner Tree problem as defined by Hauptmann and show that the problem is APX-hard. Copyright © 2020, The Authors. All rights reserved.

关键词： Approximation algorithms