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

Can quantum search accelerate evolutionary algorithms? 10

学校读者我要写书评

暂无评论

Can quantum search accelerate evolutionary algorithms?

12th Annual Genetic and Evolutionary Computation Conference, GECCO-2010

作者： Johannsen, Daniel Kurur, Piyush P. Lengler, Johannes Max Planck Institute for Informatics Department of Algorithms and Complexity Saarbrücken Germany Dept. of Comp. Sei. and Engg. Indian Institute of Technology Kanpur Kanpur UP 208016 India Department of Mathematics Saarland University Saarbrücken Germany

ISBN: (纸本)9781450300728

In this article, we formulate for the first time the notion of a quantum evolutionary algorithm. In fact we define a quantum analogue for any elitist (1+1) randomized search heuristic. The quantum evolutionary algorithm, which we call (1+1) quantum evolutionary algorithm (QEA), is the quantum version of the classical (1+1) evolutionary algorithm (EA), and runs only on a quantum computer. It uses Grover search [13] to accelerate the search for improved offsprings. To understand the speedup of the (1+1) QEA over the (1+1) EA, we study the three well known pseudo-Boolean optimization problems ONEMAX, LEADINGONES, and DISCREPANCY. We show that although there is a speedup in the case of ONEMAX and LEADINGONES in the quantum setting, the speedup is less than quadratic. For DISCREPANCY, we show that the speedup is at best constant. The reason for this inconsistency is due to the difference in the probability of making a successful mutation. On the one hand, if the probability of making a successful mutation is large then quantum acceleration does not help much. On the other hand, if the probabilities of making a successful mutation is small then quantum enhancement indeed helps. Copyright 2010 ACM.

关键词： Evolutionary algorithms

Reachability switching games

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Fearnley, John Gairing, Martin Mnich, Matthias Savani, Rahul University of Liverpool Liverpool United Kingdom Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany

We study the problem of deciding the winner of reachability switching games for zero-, one-, and two-player variants. Switching games provide a deterministic analogue of stochastic games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case is PSPACE-hard and in EXPTIME. For the zero-player case, we also show P-hardness for a succinctly-represented model that maintains the upper bound of NP ∩ coNP. For the one- and two-player cases, our results hold in both the natural, explicit model and succinctly-represented model. Our results show that the switching variant of a game is harder in complexity-theoretic terms than the corresponding stochastic version. © 2017, CC BY.

关键词： Model checking

A Parameterized Theory of PAC Learning

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Brand, Cornelius Ganian, Robert Simonov, Kirill Algorithms and Complexity Group TU Wien Austria Chair for Algorithm Engineering Hasso Plattner Institute Germany

Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the class P in classical computational complexity. But while the nascent theory of parameterized complexity has allowed us to push beyond the P-NP "dichotomy" in classical computational complexity and identify the exact boundaries of tractability for numerous problems, there is no analogue in the domain of sample complexity that could push beyond efficient PAC learnability. As our core contribution, we fill this gap by developing a theory of parameterized PAC learning which allows us to shed new light on several recent PAC learning results that incorporated elements of parameterized complexity. Within the theory, we identify not one but two notions of fixed-parameter learnability that both form distinct counterparts to the class FPT—the core concept at the center of the parameterized complexity paradigm—and develop the machinery required to exclude fixed-parameter learnability. We then showcase the applications of this theory to identify refined boundaries of tractability for CNF and DNF learning as well as for a range of learning problems on graphs. © 2023, CC BY.

关键词： Computational complexity

The Half-integral Erdős-Pósa Property for Non-null Cycles

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Lokshtanov, Daniel Ramanujan, M.S. Saurabh, Saket Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Sciences

A Group Labeled Graph is a pair (G, Λ) where G is an oriented graph and Λ is a mapping from the arcs of G to elements of a group. A (not necessarily directed) cycle C is called non-null if for any cyclic ordering of the arcs in C, the group element obtained by ‘adding’ the labels on forward arcs and ‘subtracting’ the labels on reverse arcs is not the identity element of the group. Non-null cycles in group labeled graphs generalize several well-known graph structures, including odd cycles. A family F of graphs has the Erdős-Pósa property, if for every integer k there exists an integer f(k, F) such that every graph G contains either k vertex-disjoint subgraphs each isomorphic to a graph in F or a set at most f(k, F) vertices intersecting every subgraph isomorphic to a graph in F. In this paper, we prove that non-null cycles on Group Labeled Graphs have the 21 -integral Erdős-Pósa property. That is, there is a function f : N → N such that for any k ∈ N, any group labeled graph (G, Λ) has a set of k non-null cycles such that each vertex of G appears in at most two of these cycles or there is a set of at most f(k) vertices that intersects every non-null cycle. Since it is known that non-null cycles do not have the Erdős-Pósa property in general, a 21 -integral Erdős-Pósa result is the best one could hope for. Copyright © 2017, The Authors. All rights reserved.

关键词： Machine learning

A Dynamic MaxSAT-based Approach to Directed Feedback Vertex Sets

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Kiesel, Rafael Schidler, André Institute of Logic and Computation Tu Wien Vienna Austria Algorithms and Complexity Group Tu Wien Vienna Austria

We propose a new approach to the Directed Feedback Vertex Set Problem (DFVSP), where the input is a directed graph and the solution is a minimum set of vertices whose removal makes the graph acyclic. Our approach, implemented in the solver DAGer, is based on two novel contributions: Firstly, we add a wide range of data reductions that are partially inspired by reductions for the similar vertex cover problem. For this, we give a theoretical basis for lifting reductions from vertex cover to DFVSP but also incorporate novel ideas into strictly more general and new DFVSP reductions. Secondly, we propose dynamically encoding DFVSP in propositional logic using cycle propagation for improved performance. Cycle propagation builds on the idea that already a limited number of the constraints in a propositional encoding is usually sufficient for finding an optimal solution. Our algorithm, therefore, starts with a small number of constraints and cycle propagation adds additional constraints when necessary. We propose an efficient integration of cycle propagation into the workflow of MaxSAT solvers, further improving the performance of our algorithm. Our extensive experimental evaluation shows that DAGer significantly outperforms the state-of-the-art solvers and that our data reductions alone directly solve many of the instances. Copyright © 2022, The Authors. All rights reserved.

关键词： Directed graphs

Worbel: Aggregating Point Labels into Word Clouds

学校读者我要写书评

暂无评论

Worbel: Aggregating Point Labels into Word Clouds

作者： Bhore, Sujoy Ganian, Robert Li, Guangping Nöllenburg, Martin Wulms, Jules Indian Institute of Technology Bombay Main Gate Rd IIT Area Powai Maharashtra Mumbai400076 India Algorithms and Complexity Group Technische Universität Wien Institute of Logic and Computation Favoritenstraße 9-11 E192-01 Wien1040 Austria

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this article, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consist of a set of points grouped into categories and our aim is to place multiple disjoint and axis-Aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing a heuristic with (optional) exact components using SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several synthetic and real-world data sets. Our experiments show that the fully heuristic approach produces solutions of comparable quality to heuristics combined with exact SAT models, while running much faster. © 2023 Copyright held by the owner/author(s).

关键词： Visualization

Worbel: Aggregating point labels into word clouds

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bhore, Sujoy Ganian, Robert Li, Guangping Nöllenburg, Martin Wulms, Jules Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Vienna Austria

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster. © 2021, CC BY.

关键词： Visualization

Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding

学校读者我要写书评

暂无评论

Improved Approximations for Vector Bin Packing via Iterative...

Annual IEEE Symposium on Foundations of Computer Science

作者： Ariel Kulik Matthias Mnich Hadas Shachnai Computer Science Department Technion Haifa Israel Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany

We study the d-DIMENSIONAL VECTOR BIN PACKING ($d \mathbf{V B P})$ problem, a generalization of BIN PACKING with central applications in resource allocation and scheduling. In $d \mathrm{VBP}$, we are given a set of items, each of which is characterized by a d-dimensional volume vector; the objective is to partition the items into a minimum number of subsets (bins), such that the total volume of items in each subset is at most 1 in each dimension. Our main result is an asymptotic approximation algorithm for d VBP that yields a ratio of $(1+\ln d-\chi(d)+\varepsilon)$ for all $d \in \mathbb{N}$ and any $\varepsilon\gt0$; here, $\chi(d)$ is some strictly positive function. This improves upon the best known asymptotic ratio of $(1+\ln d+\varepsilon)$ due to Bansal, Caprara and Sviridenko (SICOMP 2010) for any $d\gt3$. By slightly modifying our algorithm to include an initial matching phase and applying a tighter analysis, we obtain an asymptotic approximation ratio of $\left(\frac{4}{3}+\varepsilon\right)$ for the special case of $d=2$, thus substantially improving the previous best ratio of $\left(\frac{3}{2}+\varepsilon\right)$ due to Bansal, Eliáš and Khan (SODA 2016). Our algorithm iteratively solves a configuration LP relaxation for the residual instance (from previous iterations) and samples a small number of configurations based on the solution for the configuration LP. While iterative rounding was already used by Karmarkar and Karp (FOCS 1982) to establish their celebrated result for classic (one-dimensional) BIN PACKING, iterative randomized rounding is used here for the first time in the context of (VECTOR) BIN PACKING. Our results show that iterative randomized rounding is a powerful tool for approximating d VBP, leading to simple algorithms with improved approximation guarantees.

关键词：

Learning Depth Vision-Based Personalized Robot Navigation From Dynamic Demonstrations in Virtual Reality

学校读者我要写书评

暂无评论

Learning Depth Vision-Based Personalized Robot Navigation Fr...

IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

作者： Jorge de Heuvel Nathan Corral Benedikt Kreis Jacobus Conradi Anne Driemel Maren Bennewitz Humanoid Robots Lab Group for Algorithms and Complexity University of Bonn Lamarr Institute for Machine Learning and Artificial Intelligence Germany

For the best human-robot interaction experience, the robot's navigation policy should take into account personal preferences of the user. In this paper, we present a learning framework complemented by a perception pipeline to train a depth vision-based, personalized navigation controller from user demonstrations. Our virtual reality interface enables the demonstration of robot navigation trajectories under motion of the user for dynamic interaction scenarios. The novel perception pipeline enrolls a variational autoencoder in combination with a motion predictor. It compresses the perceived depth images to a latent state representation to enable efficient reasoning of the learning agent about the robot's dynamic environment. In a detailed analysis and ablation study, we evaluate different configurations of the perception pipeline. To further quantify the navigation controller's quality of personalization, we develop and apply a novel metric to measure preference reflection based on the Frechet Distance. We discuss the robot's navigation performance in various virtual scenes and demonstrate the first personalized robot navigation controller that solely relies on depth images. A supplemental video highlighting our approach is available online 1 1 Full video: ***/publications/deheuve123iros_***4.

关键词：