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

Transitions in Dynamic Point Labeling 12

学校读者我要写书评

暂无评论

Transitions in Dynamic Point Labeling

12th International Conference on Geographic Information Science, GIScience 2023

作者： Depian, Thomas Li, Guangping Nöllenburg, Martin Wulms, Jules Algorithms and Complexity Group TU Wien Austria Algorithm Engineering Group TU Dortmund Germany

ISBN: (纸本)9783959772884

The labeling of point features on a map is a well-studied topic. In a static setting, the goal is to find a non-overlapping label placement for (a subset of) point features. In a dynamic setting, the set of point features and their corresponding labels change, and the labeling has to adapt to such changes. To aid the user in tracking these changes, we can use morphs, here called transitions, to indicate how a labeling changes. Such transitions have not gained much attention yet, and we investigate different types of transitions for labelings of points, most notably consecutive transitions and simultaneous transitions. We give (tight) bounds on the number of overlaps that can occur during these transitions. When each label has a (non-negative) weight associated to it, and each overlap imposes a penalty proportional to the weight of the overlapping labels, we show that it is NP-complete to decide whether the penalty during a simultaneous transition has weight at most k. Finally, in a case study, we consider geotagged Twitter data on a map, by labeling points with rectangular labels showing tweets. We developed a prototype implementation to evaluate different transition styles in practice, measuring both number of overlaps and transition duration. © Thomas Depian, Guangping Li, Martin Nöllenburg, and Jules Wulms.

关键词： Information retrieval

Transitions in Dynamic Point Labeling

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Depian, Thomas Li, Guangping Nöllenburg, Martin Wulms, Jules Algorithms and Complexity Group TU Wien Vienna Austria Algorithm Engineering Group TU Dortmund Dortmund Germany

The labeling of point features on a map is a well-studied topic. In a static setting, the goal is to find a non-overlapping label placement for (a subset of) point features. In a dynamic setting, the set of point features and their corresponding labels change, and the labeling has to adapt to such changes. To aid the user in tracking these changes, we can use morphs, here called transitions, to indicate how a labeling changes. Such transitions have not gained much attention yet, and we investigate different types of transitions for labelings of points, most notably consecutive transitions and simultaneous transitions. We give (tight) bounds on the number of overlaps that can occur during these transitions. When each label has a (non-negative) weight associated to it, and each overlap imposes a penalty proportional to the weight of the overlapping labels, we show that it is NP-complete to decide whether the penalty during a simultaneous transition has weight at most k. Finally, in a case study, we consider geotagged Twitter data on a map, by labeling points with rectangular labels showing tweets. We developed a prototype implementation to evaluate different transition styles in practice, measuring both number of overlaps and transition duration. Copyright © 2022, The Authors. All rights reserved.

关键词：

Generating All Invertible Matrices by Row Operations 35

学校读者我要写书评

暂无评论

Generating All Invertible Matrices by Row Operations

35th International Symposium on algorithms and Computation, ISAAC 2024

作者： Gregor, Petr Hoang, Hung P. Merino, Arturo Mička, Ondřej Department of Theoretical Computer Science and Mathematical Logic Charles University Prague Czech Republic Algorithm and Complexity Group Faculty of Informatics TU Wien Austria Institute of Engineering Sciences Universidad de O’Higgins Rancagua Chile

ISBN: (纸本)9783959773546

We show that all invertible n × n matrices over any finite field Fq can be generated in a Gray code fashion. More specifically, there exists a listing such that (1) each matrix appears exactly once, and (2) two consecutive matrices differ by adding or subtracting one row from a previous or subsequent row, or by multiplying or dividing a row by the generator of the multiplicative group of Fq. This even holds in the more general setting where the pairs of rows that can be added or subtracted are specified by an arbitrary transition tree that has to satisfy some mild constraints. Moreover, we can prescribe the first and the last matrix if n ≥ 3, or n = 2 and q > 2. In other words, the corresponding flip graph on all invertible n × n matrices over Fq is Hamilton connected if it is not a cycle. This solves yet another special case of Lovász conjecture on Hamiltonicity of vertex-transitive graphs. © Petr Gregor, Hung P. Hoang, Arturo Merino, and Ondřej Mička.

关键词： Matrix algebra

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

SIGNOTOPES WITH FEW PLUS SIGNS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bergold, Helena Egeling, Lukas Hoang, Hung P. Institut für Informatik Freie Universität Berlin Germany Department of Computer Science ETH Zurich Switzerland Algorithm and Complexity Group Faculty of Informatics TU Wien Austria

Arrangements of pseudohyperplanes are widely studied in computational geometry. A rich subclass of pseudohyerplane arrangements, which has gained more attention in recent years, is the so-called signotopes. Introduced by Manin and Schechtman (1989), the higher Bruhat order is a natural order of r-signotopes on n elements, with the signotope corresponding to the cyclic arrangement as the minimal element. In this paper, we show that the lower (and by symmetry upper) levels of this higher Bruhat order contain the same number of elements for a fixed difference n − r. This result implies that given the difference d = n − r and p, the number of one-element extensions of the cyclic arrangement of n hyperplanes in Rd with at most p points on one side of the extending pseudohyperplane does not depend on n, as long as n ≥ d + p. © 2024, CC BY-SA.

关键词： Computational geometry

GENERATING ALL INVERTIBLE MATRICES BY ROW OPERATIONS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Gregor, Petr Hoang, Hung P. Merino, Arturo Mička, Ondřej Department of Theoretical Computer Science and Mathematical Logic Charles University Prague Czech Republic Algorithm and Complexity Group Faculty of Informatics TU Wien Austria Engineering Institute Universidad de O'Higgins Rancagua Chile

We show that all invertible n×n matrices over any finite field Fq can be generated in a Gray code fashion. More specifically, there exists a listing such that (1) each matrix appears exactly once, and (2) two consecutive matrices differ by adding or subtracting one row from a previous or subsequent row, or by multiplying or dividing a row by the generator of the multiplicative group of Fq. This even holds in the more general setting where the pairs of rows that can be added or subtracted are specified by an arbitrary transition tree that has to satisfy some mild constraints. Moreover, we can prescribe the first and the last matrix if n ≥ 3, or n = 2 and q > 2. In other words, the corresponding flip graph on all invertible n × n matrices over Fq is Hamilton connected if it is not a cycle. This solves yet another special case of Lovász conjecture on Hamiltonicity of vertex-transitive graphs. © 2024, CC BY-NC-ND.

关键词： Matrix algebra

Single-Peaked Opinion Updates

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bredereck, Robert George, Anne-Marie Israel, Jonas Kellerhals, Leon Algorithm Engineering Humboldt-Universität Berlin Germany Institut für Informatik TU Clausthal Germany Analytical Solutions and Reasoning University of Oslo Germany Research Group Efficient Algorithms Technische Universität Berlin Germany Algorithmics and Computational Complexity Technische Universität Berlin Germany

We consider opinion diffusion for undirected networks with sequential updates when the opinions of the agents are single-peaked preference rankings. Our starting point is the study of preserving single-peakedness. We identify voting rules that, when given a single-peaked profile, output at least one ranking that is single peaked w.r.t. a single-peaked axis of the input. For such voting rules we show convergence to a stable state of the diffusion process that uses the voting rule as the agents’ update rule. Further, we establish an efficient algorithm that maximises the spread of extreme opinions. Copyright © 2022, The Authors. All rights reserved.

关键词： Machine learning

Computing the degreewidth of a digraph is hard

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Aboulker, Pierre Oijid, Nacim Petit, Robin Rocton, Mathis Simon, Christopher-Lloyd DIENS École normale supérieure CNRS PSL University Paris France Univ Lyon CNRS INSA Lyon UCBL Centrale Lyon Univ Lyon 2 LIRIS UMR5205 VilleurbanneF-69622 France Computer Science Department Université Libre de Bruxelles Brussels Belgium Algorithm and Complexity Group TU Wien Vienna Austria The Pennsylvania State University Department of Mathematics United States

Given a digraph, an ordering of its vertices defines a backedge graph, namely the undirected graph whose edges correspond to the arcs pointing backwards with respect to the order. The degreewidth of a digraph is the minimum over all ordering of the maximum degree of the backedge graph. We answer an open question by Keeney and Lokshtanov [WG 2024], proving that it is NP-hard to determine whether an oriented graph has degreewidth at most 1, which settles the last open case for oriented graphs. We complement this result with a general discussion on parameters defined using backedge graphs and their relations to classical parameters. © 2024, CC BY-NC-ND.

关键词： Undirected graphs