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

arXiv 2023年

作者： Dobler, Alexander Nöllenburg, Martin Stojanovic, Daniel Villedieu, Anaïs Wulms, Jules Algorithms and Complexity Group TU Wien Austria

Storyline visualizations are a popular way of visualizing characters and their interactions over time: Characters are drawn as x-monotone curves and interactions are visualized through close proximity of the corresponding character curves in a vertical strip. Existing methods to generate storylines assume a total ordering of the interactions, although real-world data often do not contain such a total order. Instead, multiple interactions are often grouped into coarser time intervals such as years. We exploit this grouping property by introducing a new model called storylines with time intervals and present two methods to minimize the number of crossings and horizontal space usage. We then evaluate these algorithms on a small benchmark set to show their effectiveness. © 2023, CC BY.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Evaluation of a c-Load-Collision-Protocol for Load-Balancing in Interactive Environments

Evaluation of a c-Load-Collision-Protocol for Load-Balancing...

引用

International Conference on Networking, Architecture, and Storage (NAS)

作者： Tim Süß Timo Wiesemann Matthias Fischer University of Paderborn Algorithms and Complexity Paderborn Germany

Many professional cluster systems consist of nodes with different hardware configurations. Such heterogeneous environments require different load-balancing techniques than homogenous environments. The c-load-collision-protocol is able to achieve good results for data-management purposes. Using this protocol, we propose a way for load-balancing in interactive rendering environments. For this work, we implemented a parallel rendering system and took different picking strategies into account to compare the results. The advantage of our approach compared to other approaches is that we group the available nodes of a cluster into two different categories, based on the hardware abilities. Some nodes are used solely for rendering, while others serve as secondary storage and to assist the former ones by performing auxiliary calculations.

关键词： Rendering (computer graphics) Protocols Tiles Data visualization Hardware Random access memory

来源：评论

学校读者我要写书评

暂无评论

New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines 34

New Support Size Bounds for Integer Programming, Applied to ...

引用

34th International Symposium on algorithms and Computation, ISAAC 2023

作者： Berndt, Sebastian Brinkop, Hauke Jansen, Klaus Mnich, Matthias Stamm, Tobias Institute for Theoretical Computer Science University of Lübeck Germany Kiel University Germany Hamburg University of Technology Institute for Algorithms and Complexity Germany

ISBN: (纸本)9783959772891

Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows that any feasible integer linear program (ILP) has a solution with support size s ≤ 2m · log(4m∆), where m is the number of constraints, and ∆ is the largest absolute coefficient in any constraint. Our main combinatorial result are improved support size bounds for ILPs. We show that any ILP has a solution with support size s ≤ m · (log(3Amax) + plog(Amax)), where Amax:= A1 denotes the 1-norm of the constraint matrix A. Furthermore, we show support bounds in the linearized form s ≤ 2m · log(1.46Amax). Our upper bounds also hold with Amax replaced by √m∆, which improves on the previously best constants in the linearized form. Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. We design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||Cmax). Our EPTAS yields a (1 + Ε)-approximation for Q||Cmax on N jobs in time 2O(1/Ε log3(1/Ε) log(log(1/Ε))) + O(N), which improves over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020) with run time 2O(1/Ε log4(1/Ε)) + NO(1) . Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation which greatly benefits from the small support. © Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich, and Tobias Stamm;licensed under Creative Commons License CC-BY 4.0.

关键词： Integer programming

来源：评论

学校读者我要写书评

暂无评论

MySemCloud: Semantic-aware Word Cloud Editing

arXiv

引用

arXiv 2023年

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

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

关键词： Visualization

来源：评论

学校读者我要写书评

暂无评论

Small resolution proofs for QBF using dependency treewidth

arXiv

引用

arXiv 2017年

作者： Eiben, Eduard Ganian, Robert Ordyniak, Sebastian Algorithms and Complexity Group TU Wien Vienna Austria

In spite of the close connection between the evaluation of quantified Boolean formulas (QBF) and propositional satisfiability (SAT), tools and techniques which exploit structural properties of SAT instances are known to fail for QBF. This is especially true for the structural parameter treewidth, which has allowed the design of successful algorithms for SAT but cannot be straightforwardly applied to QBF since it does not take into account the interdependencies between quantified variables. In this work we introduce and develop dependency treewidth, a new structural parameter based on treewidth which allows the efficient solution of QBF instances. Dependency treewidth pushes the frontiers of tractability for QBF by overcoming the limitations of previously introduced variants of treewidth for QBF. We augment our results by developing algorithms for computing the decompositions that are required to use the parameter. Copyright © 2017, The Authors. All rights reserved.

关键词： Parameter estimation

来源：评论

学校读者我要写书评

暂无评论

Model-Checking Strategic Ability and Knowledge of the Past of Communicating Coalitions

引用

6th International Workshop on Declarative Agent Language and Technologies

作者： Guelev, Dimitar P. Dima, Catalin Bulgarian Acad Sci Inst Math & Informat BG-1040 Sofia Bulgaria Univ Paris XII Lab Algorithms Complexity & Log F-94010 Creteil France

ISBN: (纸本)9783540939191

We propose a variant of alternating time temporal logic (ATL) with imperfect information, perfect recall, episteinic modalities for the past and saralegies which are required to be uniform with respect to distributed knowledge. The model-checking problem about ATL with perfect recall and imperfect information is believed to be unsolvable whereas in our setting it is solvable because of the uniformity of able strategies. We propose a model-checking algorithm for that system, which exploits the interaction. between the cooperation modalities and the epistemic modality for the past. This interaction allows every expressible goal phi to be treated as the episteinic goal of (eventually) establishing that p holds and thus enables the handling of the cooperation modalities in a streamlined way.

关键词： Model checking

来源：评论

学校读者我要写书评

暂无评论

Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts

arXiv

引用

arXiv 2022年

作者： Brand, Cornelius Ceylan, Esra Ganian, Robert Hatschka, Christian Korchemna, Viktoriia Algorithms and Complexity Group TU Wien Vienna Austria

Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for NP-hard graph problems. For problems that are W[1]-hard parameterized by treewidth, a natural alternative would be to use a suitable analogue of treewidth that is based on edge cuts instead of vertex separators. While tree-cut width has been coined as such an analogue of treewidth for edge cuts, its algorithmic applications have often led to disappointing results: out of twelve problems where one would hope for fixed-parameter tractability parameterized by an edge-cut based analogue to treewidth, eight were shown to be W[1]-hard parameterized by tree-cut width. As our main contribution, we develop an edge-cut based analogue to treewidth called edge-cut width. Edge-cut width is, intuitively, based on measuring the density of cycles passing through a spanning tree of the graph. Its benefits include not only a comparatively simple definition, but mainly that it has interesting algorithmic properties: it can be computed by a fixed-parameter algorithm, and it yields fixed-parameter algorithms for all the aforementioned problems where tree-cut width failed to do so. © 2022, CC BY.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for Queue Layouts 28th

Parameterized Algorithms for Queue Layouts

引用

28th International Symposium on Graph Drawing and Network Visualization, GD 2020

作者： Bhore, Sujoy Ganian, Robert Montecchiani, Fabrizio Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria Bruxelles Belgium Dipartimento di Ingegneria Università degli Studi di Perugia Perugia Italy

ISBN: (纸本)9783030687656

An h-queue layout of a graph G consists of a linear order of its vertices and a partition of its edges into h queues, such that no two independent edges of the same queue nest. The minimum h such that G admits an h-queue layout is the queue number of G. We present two fixed-parameter tractable algorithms that exploit structural properties of graphs to compute optimal queue layouts. As our first result, we show that deciding whether a graph G has queue number 1 and computing a corresponding layout is fixed-parameter tractable when parameterized by the treedepth of G. Our second result then uses a more restrictive parameter, the vertex cover number, to solve the problem for arbitrary h. © 2020, Springer Nature Switzerland AG.

关键词： Parameter estimation

来源：评论

学校读者我要写书评

暂无评论

Optimizing the layout of 1000 wind turbines

Optimizing the layout of 1000 wind turbines

引用

European Wind Energy Conference and Exhibition 2011, EWEC 2011

作者： Wagner, Markus Veeramachaneni, Kalyan Neumann, Frank O'Reilly, Una-May Algorithms and Complexity Max Planck Institute for Informatics Germany Massachusetts Institute of Technology CSAIL United States School of Computer Science University of Adelaide Australia

ISBN: (纸本)9781618399915

In this paper we demonstrate an accurate, efficient, and parallelizable optimization algorithm for the layout of hundreds, then 1000, turbines. It is modular and therefore allows different wake effect models to be incorporated. Its computational cost is a relation which depends upon how many candidate layouts it investigates and the complexity of its wake loss calculation. We demonstrate how well it maximizes energy capture and show how it allows one to examine how wake loss scales with energy capture and number of turbines. Keywords: Wind farm design, output maximization, wake consideration, Covariance Matrix Adaptation, Evolutionary strategy.

关键词： Evolutionary algorithms

来源：评论

学校读者我要写书评

暂无评论

On Erdős–Szekeres-Type Problems for k-convex Point Sets 1

引用

30th International Workshop on Combinatorial algorithms, IWOCA 2019

作者： Balko, Martin Bhore, Sujoy Martínez Sandoval, Leonardo Valtr, Pavel Department of Applied Mathematics Charles University Prague Czech Republic Algorithms and Complexity Group TU Wien Vienna Austria Sorbonne Université Paris France

ISBN: (数字)9783030250058

ISBN: (纸本)9783030250041

We study Erdős–Szekeres-type problems for k-convex point sets, a recently introduced notion that naturally extends the concept of convex position. A finite set S of n points is k-convex if there exists a spanning simple polygonization of S such that the intersection of any straight line with its interior consists of at most k connected components. We address several open problems about k-convex point sets. In particular, we extend the well-known Erdős–Szekeres Theorem by showing that, for every fixed k ∈ N, every set of n points in the plane in general position (with no three collinear points) contains a k-convex subset of size at least Ω(logk n). We also show that there are arbitrarily large 3-convex sets of n points in the plane in general position whose largest 1-convex subset has size O(log n). This gives a solution to a problem posed by Aichholzer et al.Â [2]. We prove that there is a constant c > 0 such that, for every n ∈ N, there is a set S of n points in the plane in general position such that every 2-convex polygon spanned by at least c · log n points from S contains a point of S in its interior. This matches an earlier upper bound by Aichholzer et al.Â [2] upÂ to a multiplicative constant and answers another of their open problems. © 2019, Springer Nature Switzerland AG.

关键词： Geometry

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：