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

Using fast matrix multiplication in bio-inspired computation for complex optimization problems

学校读者我要写书评

暂无评论

Using fast matrix multiplication in bio-inspired computation...

Congress on Evolutionary Computation

作者： Florian Diedrich Frank Neumann Institut für Informatik Christian-Albrechts-Universität Kiel Kiel Germany Algorithms and Complexity Group Max Planck Institut für Informatik Saarbrucken Germany

Population-based search heuristics such as evolutionary algorithms or ant colony optimization have been widely used to tackle complex problems in combinatorial optimization. In many cases these problems involve the optimization of an objective function subject to a set of constraints which is very large. In this paper, we examine how population-based search heuristics can be sped up by making use of fast matrix multiplication algorithms. First, we point out that this approach is applicable to the wide class of problems which can be expressed as an Integer Linear Program (ILP). Later on, we investigate the speedup that can be gained by the proposed approach in our experimental studies for the multidimensional knapsack problem.

关键词： Optimization Runtime Evolutionary computation Algorithm design and analysis Layout Indexes Ant colony optimization

Perfect Pseudo-Matchings in cubic graphs

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Fleischner, Herbert Behrooz Bagheri, Gh. Klocker, Benedikt Algorithms and Complexity Group Vienna University of Technology Favoritenstrasse 9-11 Vienna1040 Department of Mathematics West Virginia University MorgantownWV26506-6310 United States

A perfect pseudo-matching M in a cubic graph G is a spanning subgraph of G such that every component of M is isomorphic to K2or to K1,3. In view of snarks G with dominating cycle C, this is a natural generalization of perfect matchings since G\E(C) is a perfect pseudo-matching. Of special interest are such M where G/M is planar because such G have a cycle double cover. We show that various well known classes of snarks contain planarizing perfect pseudo-matchings, and that there are at least as many snarks with planarizing perfect pseudo-matchings as there are cyclically 5-edge-connected *** Codes 05C45, 05C10, 05C60 Copyright © 2019, The Authors. All rights reserved.

关键词： Graph theory

Clustered Planarity Variants for Level Graphs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Fink, Simon D. Pfretzschner, Matthias Rutter, Ignaz Sieper, Marie Diana Algorithms and Complexity Group Technische Universität Wien Austria Faculty of Computer Science and Mathematics University of Passau Germany Institute of Computer Science University of Würzburg Germany

We consider variants of the clustered planarity problem for level-planar drawings. So far, only convex clusters have been studied in this setting. We introduce two new variants that both insist on a level-planar drawing of the input graph but relax the requirements on the shape of the clusters. In unrestricted Clustered Level Planarity (uCLP) we only require that they are bounded by simple closed curves that enclose exactly the vertices of the cluster and cross each edge of the graph at most once. The problem y-monotone Clustered Level Planarity (y-CLP) requires that additionally it must be possible to augment each cluster with edges that do not cross the cluster boundaries so that it becomes connected while the graph remains level-planar, thereby mimicking a classic characterization of clustered planarity in the level-planar setting. We give a polynomial-time algorithm for uCLP if the input graph is biconnected and has a single source. By contrast, we show that y-CLP is hard under the same restrictions and it remains NP-hard even if the number of levels is bounded by a constant and there is only a single non-trivial cluster. © 2024, CC BY.

关键词： Polynomial approximation

学校读者我要写书评

暂无评论

Minimum Link Fencing

arXiv 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

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. © 2022, CC BY.

关键词： Computational geometry

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

On Finding Hamiltonian Cycles in Barnette Graphs

学校读者我要写书评

暂无评论

arXiv 2022年

In this paper we deal with hamiltonicity in planar cubic graphs G having a facial 2−factor Q via (quasi) spanning trees of faces in G/Q and study the algorithmic complexity of finding such (quasi) spanning trees of faces. Moreover, we show that if Barnette’s Conjecture is false, then hamiltonicity in 3−connected planar cubic bipartite graphs is an NP-complete problem. © 2022, CC0.

关键词： Computational complexity

Scheduling with non-renewable resources: Minimizing the sum of completion times

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Bércziy, Kristóf Királyz, Tamás Omlorx, Simon MTA-ELTE Egerváry Research Group Department of Operations Research Eötvös Loránd University Budapest Tu Hamburg Institute for Algorithms and Complexity Hamburg

The paper considers single-machine scheduling problems with a non-renewable resource. In this setting, we are given a set jobs, each of which is characterized by a processing time, a weight, and the job also has some resource requirement. At fixed points in time, a certain amount of the resource is made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that at any time their resource requirement does not exceed the available amounts of resources. The objective that we consider here is the minimization of the sum of weighted completion times. We give polynomial approximation algorithms and complexity results for single scheduling machine problems. In particular, we show strong NP-hardness of the case of unit resource requirements and weights (1|rm = 1, aj= 1| £ Cj), thus answering an open question of Györgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a 3/2-approximation for the same problem. We give simple constant factor approximations and a more complicated PTAS for the case of 0 processing times (1|rm = 1,pj= 0wjCj). We close the paper by proposing a new variant of the problem in which the resource arrival times are unknown. A 4-approximation is presented for this variant, together with an (4 - ϵ)-inapproximability result. Copyright © 2019, The Authors. All rights reserved.

关键词： Approximation algorithms

K-D trees are better when cut on the longest side

学校读者我要写书评

暂无评论

K-D trees are better when cut on the longest side

8th Annual European Symposium on algorithms, ESA 2000

作者： Dickerson, Matthew Duncan, Christian A. Goodrich, Michael T. Dept of Math and Comp Sci Middlebury College MiddleburyVT05753 United States Algorithms and Complexity Group Max-Planck-Inst. Für Informatik SaarbrückenD-66123 Germany Dept of Comp. Sci Johns Hopkins Univ BaltimoreMD21218 United States

ISBN: (纸本)354041004X

We show that a popular variant of the well known k-d tree data structure satisfies an important packing lemma. This variant is a binary spatial partitioning tree T defined on a set of n points in IRd, for fixed d ≥ 1, using the simple rule of splitting each node’s hyperrectangular region with a hyperplane that cuts the longest side. An interesting consequence of the packing lemma is that standard algorithms for performing approximate nearest-neighbor searching or range searching queries visit at most O(logd–1n) nodes of such a tree T in the worst case. Traditionally, many variants of k-d trees have been empirically shown to exhibit polylogarithmic performance, and under certain restrictions in the data distribution some theoretical expected case results have been proven. This result, however, is the first one proving a worst-case polylogarithmic time bound for approximate geometric queries using the simple k-d tree data structure. © Springer-Verlag Berlin Heidelberg 2000.

关键词： Nearest neighbor search

The Fine-Grained complexity of Graph Homomorphism Parameterized by Clique-Width

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Ganian, Robert Hamm, Thekla Korchemna, Viktoriia Okrasa, Karolina Simonov, Kirill Algorithms and Complexity Group TU Wien Vienna Austria Faculty of Matematics and Information Science Warsaw University of Technology Warsaw Poland Faculty of Mathematics Informatics and Mechanics University of Warsaw Poland

The generic homomorphism problem, which asks whether an input graph G admits a homomorphism into a fixed target graph H, has been widely studied in the literature. In this article, we provide a fine-grained complexity classification of the running time of the homomorphism problem with respect to the clique-width of G (denoted cw) for virtually all choices of H under the Strong Exponential Time Hypothesis. In particular, we identify a property of H called the signature number s(H) and show that for each H, the homomorphism problem can be solved in time O∗(s(H)cw). Crucially, we then show that this algorithm can be used to obtain essentially tight upper bounds. Specifically, we provide a reduction that yields matching lower bounds for each H that is either a projective core or a graph admitting a factorization with additional properties—allowing us to cover all possible target graphs under long-standing *** Codes 68R10 © 2022, CC BY.

关键词：