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

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2025年 129卷

作者： Depian, Thomas Noellenburg, Martin Terziadis, Soeren Wallinger, Markus TU Wien Algorithms & Complex Grp Vienna Austria TU Eindhoven Algorithms Cluster Eindhoven Netherlands Tech Univ Munich Chair Efficient Algorithms Munich Germany

Boundary labeling is a technique in computational geometry used to label sets of features in an illustration. It involves placing labels along an axis-parallel bounding box and connecting each label with its corresponding feature using non-crossing leader lines. Although boundary labeling is well-studied, semantic constraints on the labels have not been investigated thoroughly. In this paper, we introduce grouping and ordering constraints in boundary labeling: Grouping constraints enforce that all labels in a group are placed consecutively on the boundary, and ordering constraints enforce a partial order over the labels. We show that it is NP-hard to find a labeling for arbitrarily sized labels with unrestricted positions along one side of the boundary. However, we obtain polynomialtime algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Furthermore, we show that finding a labeling on two opposite sides of the boundary is NP-complete, even for uniform-height labels and finite label positions. Finally, we experimentally confirm that our approach has also practical relevance. (c) 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Boundary labeling Grouping constraints Ordering constraints Dynamic programming Computational complexity

来源：评论

学校读者我要写书评

暂无评论

How Do People Perceive Bundling? An Experiment 25

How Do People Perceive Bundling? An Experiment

引用

Proceedings of the 2025 CHI Conference on Human Factors in Computing Systems

作者： Markus Wallinger Osman Akbulut Kabir Ahmed Rufai Helen C. Purchase Daniel Archambault Chair for Efficient Algorithms Technical University of Munich Munich Germany Department of Computer Engineering Faculty of Engineering Duzce University Duzce Turkiye Faculty of Information Technology Monash University Melborne Victoria Australia Faculty of Information Technology Monash University Melbourne Australia Newcastle University Newcastle United Kingdom

来源：评论

学校读者我要写书评

暂无评论

GdMetriX - A NetworkX Extension For Graph Drawing Metrics 32

GdMetriX - A NetworkX Extension For Graph Drawing Metrics

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Nöllenburg, Martin Röder, Sebastian Wallinger, Markus Algorithms and Complexity Group TU Wien Austria TU Wien Austria Chair for Efficient Algorithms Technical University of Munich Germany

ISBN: (纸本)9783959773430

networkX is a well-established Python library for network analysis. With gdMetriX, we aim to extend the functionality of networkX and provide common quality metrics used in the field of graph drawing, such as the number of crossings or the angular resolution. In addition, the package provides easy-to-use access to the graph datasets provided by the 'Graph Layout Benchmark Datasets' project from the Northeastern University Visualization Lab. © Martin Nöllenburg, Sebastian Röder, and Markus Wallinger.

关键词： Data visualization

来源：评论

学校读者我要写书评

暂无评论

Refining Tournament Solutions via Margin of Victory 34

Refining Tournament Solutions via Margin of Victory

引用

34th AAAI Conference on Artificial Intelligence / 32nd Innovative Applications of Artificial Intelligence Conference / 10th AAAI Symposium on Educational Advances in Artificial Intelligence

作者： Brill, Markus Schmidt-Kraepelin, Ulrike Suksompong, Warut Tech Univ Berlin Chair Efficient Algorithms Berlin Germany Univ Oxford Dept Comp Sci Oxford England

ISBN: (纸本)9781577358350

Tournament solutions are frequently used to select winners from a set of alternatives based on pairwise comparisons between alternatives. Prior work has shown that several common tournament solutions tend to select large winner sets and therefore have low discriminative power. In this paper, we propose a general framework for refining tournament solutions. In order to distinguish between winning alternatives, and also between non-winning ones, we introduce the notion of margin of victory (MoV) for tournament solutions. MoV is a robustness measure for individual alternatives: For winners, the MoV captures the distance from dropping out of the winner set, and for non-winners, the distance from entering the set. In each case, distance is measured in terms of which pairwise comparisons would have to be reversed in order to achieve the desired outcome. For common tournament solutions, including the top cycle, the uncovered set, and the Banks set, we determine the complexity of computing the MoV and provide worst-case bounds on the MoV for both winners and non-winners. Our results can also be viewed from the perspective of bribery and manipulation.

关键词： Refining

来源：评论

学校读者我要写书评

暂无评论

Boundary Labeling in a Circular Orbit 32

Boundary Labeling in a Circular Orbit

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Bonerath, Annika Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Wulms, Jules University of Bonn Germany Algorithms and Complexity Group TU Wien Austria TU Eindhoven Netherlands Chair for Efficient Algorithms TU Munich Germany

ISBN: (纸本)9783959773430

Boundary labeling is a well-known method for displaying short textual labels for a set of point features in a figure alongside the boundary of that figure. Labels and their corresponding points are connected via crossing-free leaders. We propose orbital boundary labeling as a new variant of the problem, in which (i) the figure is enclosed by a circular contour and (ii) the labels are placed as disjoint circular arcs in an annulus-shaped orbit around the contour. The algorithmic objective is to compute an orbital boundary labeling with the minimum total leader length. We identify several parameters that define the corresponding problem space: two leader types (straight or orbital-radial), label size and order, presence of candidate label positions, and constraints on where a leader attaches to its label. Our results provide polynomial-time algorithms for many variants and NP-hardness for others, using a variety of geometric and combinatorial insights. © Annika Bonerath, Martin Nöllenburg, Soeren Terziadis, Markus Wallinger, and Jules Wulms.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

On Mechanism Design Without Payments for Throughput Maximization

On Mechanism Design Without Payments for Throughput Maximiza...

引用

IEEE INFOCOM Conference 2009

作者： Moscibroda, Thomas Schmid, Stefan Microsoft Res Syst & Networking Res Grp Redmond WA USA Tech Univ Munich Chair Efficient Algorithms Munich Germany

ISBN: (纸本)9781424435128

It is well-known that the overall efficiency of a distributed system can suffer if the participating entities seek to maximize their individual performance. Consequently, mechanisms have been designed that force the participants to behave more cooperatively. Most of these game-theoretic solutions rely on payments between participants. Unfortunately, such payments are often cumbersome to implement in practice, especially in dynamic networks and where transaction costs are high. In this paper, we investigate the potential of mechanisms which work without payments. We consider the problem of throughput maximization in multi-channel environments and shed light onto the throughput increase that can be achieved with and without payments. We introduce and analyze two different concepts: the worst-case leverage where we assume that players end up in the worst rational strategy profile, and the average-case leverage where player select a random non-dominated strategy. Our theoretical insights are complemented by simulations.

关键词： Throughput

来源：评论

学校读者我要写书评

暂无评论

Approval-Based Apportionment 34

Approval-Based Apportionment

引用

34th AAAI Conference on Artificial Intelligence / 32nd Innovative Applications of Artificial Intelligence Conference / 10th AAAI Symposium on Educational Advances in Artificial Intelligence

作者： Brill, Markus Goelz, Paul Peters, Dominik Schmidt-Kraepelin, Ulrike Wilkerl, Kai Tech Univ Berlin Chair Efficient Algorithms Berlin Germany Carnegie Mellon Univ Comp Sci Dept Pittsburgh PA 15213 USA

ISBN: (纸本)9781577358350

In the apportionment problem, a fixed number of seats must be distributed among parties in proportion to the number of voters supporting each party. We study a generalization of this setting, in which voters cast approval ballots over parties, such that each voter can support multiple parties. This approval-based apportionment setting generalizes traditional apportionment and is a natural restriction of approval-based multiwinner elections, where approval ballots range over individual candidates. Using techniques from both apportionment and multiwinner elections, we are able to provide representation guarantees that are currently out of reach in the general setting of multiwinner elections: First, we show that core-stable committees are guaranteed to exist and can be found in polynomial time. Second, we demonstrate that extended justified representation is compatible with committee monotonicity.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Combinatorial Agency with Audits

Combinatorial Agency with Audits

引用

International Conference on Game Theory for Networks

作者： Eidenbenz, Raphael Schmid, Stefan ETH Comp Engn & Networks Lab TIK Zurich Switzerland Tech Univ Munich Comp Sci Dept Chair Efficient Algorithms Munich Germany

ISBN: (纸本)9781424441761

This paper studies the question of how to overcome inefficiencies due to hidden actions in a rational milieu, such as a grid computing system with open clientele. We consider the so-called principal-agent model known from economic theory, where the members (or agents) of a distributed system collaborate in complex ways. We adopt the perspective of the principal and investigate auditing mechanisms that incentivize participants to contribute more to a common project. As conducting audits might be costly, the principal must balance the tradeoff between low auditing costs and the level of incentives offered to the participants to exert high effort. We present optimal solutions for this optimization problem in scenarios, where the project success either depends on all, on any or on the majority of the participants succeeding in their subtask. In the first case, we further find that with an increasing principal valuation, there is exactly one transition point where the optimal choices for achieving the maximal principal utility switch. Compared to a combinatorial agency without the leverage of audits, this transition occurs earlier.

关键词： Grid computing

来源：评论

学校读者我要写书评

暂无评论

Speed Dating Despite Jammers

引用

5th IEEE International Conference on Distributed Computing in Sensor Systems

作者： Meier, Dominic Pignolet, Yvonne Anne Schmid, Stefan Wattenhofer, Roger Swiss Fed Inst Technol Comp Engn & Networks Lab Zurich Switzerland Tech Univ Munich Chair Efficient Algorithms D-80290 Munich Germany

ISBN: (纸本)9783642020841

Many wireless standards and protocols today, such as WLAN and Bluetooth, operate on similar frequency bands. While this permits an efficient usage of the limited medium capacity, transmissions of nodes running different protocols can interfere. This paper studies how to design node discovery algorithms for wireless multichannel networks which are robust against contending protocols on the shared medium. We pursue a conservative approach and consider a Byzantine adversary who prevents the communication of our protocol on t channels in a worst-case fashion. Our model also captures disruptions controlled by an adversarial jammer. This paper presents algorithms for scenarios where t is not known. The analytical findings are complemented by simulations providing evidence that the proposed protocols perform well in practice.

关键词： Jamming

来源：评论

学校读者我要写书评

暂无评论

Random Projections and Sampling algorithms for Clustering of High-Dimensional Polygonal Curves 33

Random Projections and Sampling Algorithms for Clustering of...

引用

33rd Conference on Neural Information Processing Systems (NeurIPS)

作者： Meintrup, Stefan Munteanu, Alexander Rohde, Dennis TU Dortmund Univ Fac Comp Sci Dortmund Germany TU Dortmund Univ Dortmund Data Sci Ctr Dortmund Germany TU Dortmund Univ Chair Efficient Algorithms & Complex Theory Dortmund Germany

We study the k-median clustering problem for high-dimensional polygonal curves with finite but unbounded number of vertices. We tackle the computational issue that arises from the high number of dimensions by defining a Johnson-Lindenstrauss projection for polygonal curves. We analyze the resulting error in terms of the Frechet distance, which is a tractable and natural dissimilarity measure for curves. Our clustering algorithms achieve sublinear dependency on the number of input curves via subsampling. Also, we show that the Frechet distance can not be approximated within any factor of less than root 2 by probabilistically reducing the dependency on the number of vertices of the curves. As a consequence we provide a fast, CUDA-parallelized version of the Alt and Godau algorithm for computing the Frechet distance and use it to evaluate our results empirically.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：