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

An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling

ACM Journal of Experimental Algorithmics 2022年第1期27卷 1-36页

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal Bypass Road Bhauri Madhya Pradesh Bhopal462066 India TU Wien Algorithms and Complexity Group Favoritenstraße 9-11 Vienna1040 Austria

Map labeling is a classical problem in cartography and geographic information systems that asks to place labels for area, line, and point features, with the goal to select and place the maximum number of independent (i.e., overlap-free) labels. A practically interesting case is point labeling with axis-parallel rectangular labels of common size. In a fully dynamic setting, at each timestep, either a new label appears or an existing label disappears. Then, the challenge is to maintain a maximum cardinality subset of pairwise independent labels with sublinear update time. Motivated by this, we study the maximal independent set (MIS) and maximum independent set (Max-IS) problems on fully dynamic (insertion/deletion model) sets of axis-parallel rectangles of two types: (i) uniform height and width and (ii) uniform height and arbitrary width;both settings can be modeled as rectangle intersection graphs. We present the first deterministic algorithm for maintaining an MIS (and thus a 4-approximate Max-IS) of a dynamic set of uniform rectangles with polylogarithmic update time. This breaks the natural barrier of update time (where is the maximum degree in the graph) for vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating Max-IS and provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first give an algorithm that maintains a 4-approximate Max-IS with update time. In a subsequent algorithm, we establish the trade-off between approximation quality and update time , for . We conclude with an algorithm that maintains a 2-approximate Max-IS for dynamic sets of unit-height and arbitrary-width rectangles with update time, where is the maximum size of an independent set of rectangles stabbed by any horizontal line. We implement our algorithms and report the results of an experimental comparison exploring the trade-off between solution quality and update time for synthetic and real-world map labeling instances. We

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards Faster Reasoners by Using Transparent Huge Pages 26th

Towards Faster Reasoners by Using Transparent Huge Pages

引用

26th International Conference on Principles and Practice of Constraint Programming, CP 2020

作者： Fichte, Johannes K. Manthey, Norbert Stecklina, Julian Schidler, André School of Engineering Sciences TU Dresden Dresden Germany Dresden Germany Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030584740

Various state-of-the-art automated reasoning (AR) tools are widely used as backend tools in research of knowledge representation and reasoning as well as in industrial applications. In testing and verification, those tools often run continuously or nightly. In this work, we present an approach to reduce the runtime of AR tools by 10% on average and up to 20% for long running tasks. Our improvement addresses the high memory usage that comes with the data structures used in AR tools, which are based on conflict driven no-good learning. We establish a general way to enable faster memory access by using the memory cache line of modern hardware more effectively. Therefore, we extend the standard C library (glibc) by dynamically allowing to use a memory management feature called huge pages. Huge pages allow to reduce the overhead that is required to translate memory addresses between the virtual memory of the operating system and the physical memory of the hardware. In that way, we can reduce runtime, which in turn decreases costs of running AR tools and applications with similar memory access patterns by linking the tool against this new glibc library when compiling it. In every day industrial applications, runtime savings allow to include more detailed verification tasks, getting better results of any-time optimization algorithms with a bound execution time, and save energy during nightly software builds. To back up the claimed speed-up, we present experimental results for tools that are commonly used in the AR community, including the domains ASP, hardware and software BMC, MaxSAT, and SAT. © 2020, Springer Nature Switzerland AG.

关键词： Cache memory

来源：评论

学校读者我要写书评

暂无评论

Non-Clashing Teaching Maps for Balls in Graphs 37

Non-Clashing Teaching Maps for Balls in Graphs

引用

37th Annual Conference on Learning Theory, COLT 2024

作者： Chalopin, Jérémie Chepoi, Victor Mc Inerney, Fionn Ratel, Sébastien Aix-Marseille Université Université de Toulon CNRS LIS Marseille France Algorithms and Complexity Group TU Wien Vienna Austria

Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and showed it to be the most efficient machine teaching model satisfying the benchmark for collusion-avoidance set by Goldman and Mathias. A teaching map T for a concept class C assigns a (teaching) set T(C) of examples to each concept C ∈ C. A teaching map is non-clashing if no pair of concepts are consistent with the union of their teaching sets. The size of a non-clashing teaching map (NCTM) T is the maximum size of a teaching set T(C), C ∈ C. The non-clashing teaching dimension NCTD(C) of C is the minimum size of an NCTM for C. NCTM+ and NCTD+(C) are defined analogously, except the teacher may only use positive examples. We study NCTMs and NCTM+s for the concept class B(G) consisting of all balls of a graph G. We show that the associated decision problem B-NCTD+ for NCTD+ is NP-complete in split, co-bipartite, and bipartite graphs. Surprisingly, we even prove that, unless the ETH fails, B-NCTD+ does not admit an algorithm running in time 22o(vc) ·nO(1), nor a kernelization algorithm outputting a kernel with 2o(vc) vertices, where vc is the vertex cover number of G. We complement these lower bounds with matching upper bounds. These are extremely rare results: it is only the second problem in NP to admit such a tight double-exponential lower bound parameterized by vc, and only one of very few problems to admit such an ETH-based conditional lower bound on the number of vertices in a kernel. For trees, interval graphs, cycles, and trees of cycles, we derive NCTM+s or NCTMs for B(G) of size proportional to its VC-dimension. For Gromov-hyperbolic graphs, we design an approximate NCTM+ for B(G) of size 2, in which only pairs of balls with Hausdorff distance larger than some constant must satisfy the non-clashing condition. © 2024 J. Chalopin, V. Chepoi, F. Mc Inerney & S. Ratel.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

MySemCloud: Semantic-aware Word Cloud Editing

MySemCloud: Semantic-aware Word Cloud Editing

引用

Pacific (formerly Asia-Pacific APVIS) Visualization Symposium

作者： Michael Huber Martin Nöllenburg Anaïs Villedieu Algorithms and Complexity Group TU Wien

Word clouds are a popular text visualization technique that summarize an input text by displaying its most important words in a compact image. The traditional layout methods do not take proximity effects between words into account; this has been improved in semantic word clouds, where relative word placement is controlled by edges in a word similarity graph. We introduce MySemCloud, a new human-in-the-loop tool to visualize and edit semantic word clouds. MySemCloud lets users perform computer-assisted local moves of words, which improve or at least retain the semantic quality. To achieve this, we construct a word similarity graph on which a system of forces is applied to generate a compact initial layout with good semantic quality. The force system also allows us to maintain these attributes after each user interaction, as well as preserve the user’s mental map. The tool provides algorithmic support for the editing operations to help the user enhance the semantic quality of the visualization, while adjusting it to their personal preference. We show that MySemCloud provides high user satisfaction as well as permits users to create layouts of higher quality than state-of-the-art semantic word cloud generation tools.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Computing Hive Plots: A Combinatorial Framework

引用

Journal of Graph algorithms and Applications 2024年第2期28卷 101-129页

作者： Nöllenburg, Martin Wallinger, Markus Algorithms and Complexity Group TU Wien Vienna Austria

Hive plots are a graph visualization style placing vertices on a set of radial axes emanating from a common center and drawing edges as smooth curves connecting their respective endpoints. In previous work on hive plots, assignment to an axis and vertex positions on each axis were determined based on selected vertex attributes and the order of axes was prespecified. Here, we present a new framework focusing on combinatorial aspects of these drawings to extend the original hive plot idea and optimize visual properties such as the total edge length and the number of edge crossings in the resulting hive plots. Our framework comprises three steps: (1) partition the vertices into multiple groups, each corresponding to an axis of the hive plot;(2) optimize the cyclic axis order to bring more strongly connected groups near each other;(3) optimize the vertex ordering on each axis to minimize edge crossings. Each of the three steps is related to a well-studied, but NP-complete computational problem. We combine and adapt suitable exact and heuristic algorithmic approaches, implement them as an instantiation of our framework, and show in a case study how it can be applied in a practical setting. Furthermore, we conduct computational experiments to gain further insights regarding the algorithmic choices of our framework. The code of the implementation and a prototype web application can be found on OSF1. © 2024, Brown University. All rights reserved.

关键词： Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Epistemic ATL with perfect recall, past and strategy contexts

Epistemic ATL with perfect recall, past and strategy context...

引用

13th International Workshop on Computational Logic in Multi-Agent Systems, CLIMA XIII

作者： Guelev, Dimitar P. Dima, Catalin Institute of Mathematics and Informatics Bulgarian Academy of Sciences Belgium Laboratory of Algorithms Complexity and Logic Université Paris Est-Créteil France

We propose an extension to epistemic ATL with perfect recall, past, and distributed knowledge by strategy contexts and demonstrate the strong completeness of a Hilbert-style proof system for its (. .)-free subset. ... 详细信息

ISBN: (纸本)9783642328961

关键词： Computers

来源：评论

学校读者我要写书评

暂无评论

Diameter and k-center in sliding windows 43

Diameter and k-center in sliding windows

引用

43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016

作者： Cohen-Addad, Vincent Schwiegelshohn, Chris Sohler, Christian Département D'informatique École Normale Supérieure Paris France Efficient Algorithms and Complexity Theory TU Dortmund Dortmund Germany

ISBN: (纸本)9783959770132

In this paper we develop streaming algorithms for the diameter problem and the k-center clustering problem in the sliding window model. In this model we are interested in maintaining a solution for the N most recent points of the stream. In the diameter problem we would like to maintain two points whose distance approximates the diameter of the point set in the window. Our algorithm computes a (3 + ϵ)-approximation and uses O(1/ϵ ln α) memory cells, where α is the ratio of the largest and smallest distance and is assumed to be known in advance. We also prove that under reasonable assumptions obtaining a (3 - ϵ)-approximation requires Ω(N1/3) space. For the k-center problem, where the goal is to find k centers that minimize the maximum distance of a point to its nearest center, we obtain a (6 + ϵ)-approximation using O(k/ϵ lnα) memory cells and a (4 + ϵ)-approximation for the special case k = 2. We also prove that any algorithm for the 2-center problem that achieves an approximation ratio of less than 4 requires Ω(N1/3) space.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Counting linear extensions: Parameterizations by treewidth 24

Counting linear extensions: Parameterizations by treewidth

引用

24th Annual European Symposium on algorithms, ESA 2016

作者： Eiben, Eduard Ganian, Robert Kangas, Kustaa Ordyniak, Sebastian Algorithms and Complexity Group TU Wien Vienna Austria Helsinki Institute for Information Technology Department of Computer Science University of Helsinki Finland

ISBN: (纸本)9783959770156

We consider the #P-complete problem of counting the number of linear extensions of a poset (#LE);a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of #LE parameterized by the well-known decompositional parameter treewidth for two natural graphical representations of the input poset, i.e., the cover and the incomparability graph. Our main result shows that #LE is fixed-parameter intractable parameterized by the treewidth of the cover graph. This resolves an open problem recently posed in the Dagstuhl seminar on Exact algorithms. On the positive side we show that #LE becomes fixed-parameter tractable parameterized by the treewidth of the incomparability graph. © Eduard Eiben, Robert Ganian, Kustaa Kangas, and Sebastian Ordyniak.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Computing Hive Plots: A Combinatorial Framework

arXiv

引用

arXiv 2023年

作者： Nöllenburg, Martin Wallinger, Markus Algorithms and Complexity Group TU Wien Austria

Hive plots are a graph visualization style placing vertices on a set of radial axes emanating from a common center and drawing edges as smooth curves connecting their respective endpoints. In previous work on hive plots, assignment to an axis and vertex positions on each axis were determined based on selected vertex attributes and the order of axes was prespecified. Here, we present a new framework focusing on combinatorial aspects of these drawings to extend the original hive plot idea and optimize visual properties such as the total edge length and the number of edge crossings in the resulting hive plots. Our framework comprises three steps: (1) partition the vertices into multiple groups, each corresponding to an axis of the hive plot;(2) optimize the cyclic axis order to bring more strongly connected groups near each other;(3) optimize the vertex ordering on each axis to minimize edge crossings. Each of the three steps is related to a well-studied, but NP-complete computational problem. We combine and adapt suitable algorithmic approaches, implement them as an instantiation of our framework and show in a case study how it can be applied in a practical setting. Furthermore, we conduct computational experiments to gain further insights regarding algorithmic choices of the framework. The code of the implementation and a prototype web application can be found on OSF1 © 2023, CC BY.

关键词： Optimization

来源：评论

学校读者我要写书评

暂无评论

Analysis of different MMAS ACO algorithms on unimodal functions and plateaus

引用

Swarm Intelligence 2009年第1期3卷 35-68页

作者： Neumann, Frank Sudholt, Dirk Witt, Carsten Department of Algorithms and Complexity Max-Planck-Institut für Informatik 66123 Saarbrücken Germany Fakultät für Informatik LS 2 Technische Universität Dortmund 44221 Dortmund Germany

Recently, the first rigorous runtime analyses of ACO algorithms appeared, covering variants of the MAX - MIN ant system and their runtime on pseudo-Boolean functions. Interestingly, a variant called 1-ANT is very sensitive to the evaporation factor while Gutjahr and Sebastiani proved partly opposite results for their variant MMASbs. These algorithms differ in their pheromone update mechanisms and, moreover, 1-ANT accepts equally fit solutions in contrast to MMASbs. By analyzing variants of MMASbs, we prove that the different behavior of 1-ANT and MMASbs results from the different pheromone update mechanisms. Building upon results by Gutjahr and Sebastiani, we extend their analyses of MMASbs to the class of unimodal functions and show improved results for test functions using new and specialized techniques;in particular, we present new lower bounds. Finally, we compare MMASbs with a variant that also accepts equally fit solutions as this enables the exploration of plateaus. For well-known plateau functions we prove that this drastically reduces the optimization time. Our findings are complemented by experiments that support our asymptotic analyses and yield additional insights. © The Author(s) 2008.

关键词： Ant colony optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：