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

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

来源：评论

学校读者我要写书评

暂无评论

A Relative Value Function Based Learning Beam Search for the Longest Common Subsequence Problem 18th

A Relative Value Function Based Learning Beam Search for th...

引用

18th International Conference on Computer Aided Systems Theory, EUROCAST 2022

作者： Huber, M. Raidl, G.R. Algorithms and Complexity Group Institute of Logic and Computation TU Wien Vienna Austria

ISBN: (纸本)9783031253119

Beam search (BS) is a well-known graph search algorithm frequently used to heuristically find good or near-optimal solutions to combinatorial optimization problems. Its most crucial component is a heuristic function that estimates the best achievable length-to-go from any state to a goal state. This function usually needs to be developed specificially for a problem at hand, which is a manual and time-consuming process. Building on previous work, we propose a Relative Value Function Based Learning Beam Search (RV-LBS) to automate this task at least partially by using a multilayer perceptron (MLP) as heuristic function, which is trained in a reinforcement learning manner on many randomly created problem instances. This MLP predicts the difference of the expected solution length from a given state to the expected average solution length of all states at a current BS level. To support the training of the MLP on the longest common subsequence (LCS) problem, a compact fixed-size encoding of the distribution of differences of remaining string lengths to the average string length at the current level is presented. Tests show that a MLP trained by RV-LBS on randomly created small-size problem instances is able to guide BS well also on larger established LCS benchmark instances. The obtained results are highly competitive to the state-of-the-art. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： Benchmarking

来源：评论

学校读者我要写书评

暂无评论

On the fine-grained parameterized complexity of partial scheduling to minimize the makespan 15

On the fine-grained parameterized complexity of partial sche...

引用

15th International Symposium on Parameterized and Exact Computation, IPEC 2020

作者： Nederlof, Jesper Swennenhuis, Céline M.F. Utrecht University Algorithms and Complexity Group Netherlands Eindhoven University of Technology Combinatorial Optimization Group Netherlands

ISBN: (纸本)9783959771726

We study a natural variant of scheduling that we call partial scheduling: In this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type f(k)nO(1) or nO(f(k)) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in P, NP-complete and fixed-parameter tractable by k, or W[1]-hard parameterized by k. Second, for many interesting cases we further investigate the run time on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an O(8kk(|V | + |E|)) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where G = (V, E) is the graph with precedence constraints. © Jesper Nederlof and Céline M. F. Swennenhuis

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Constrained Boundary Labeling 35

Constrained Boundary Labeling

引用

35th International Symposium on algorithms and Computation, ISAAC 2024

作者： Depian, Thomas Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Algorithms and Complexity Group TU Wien Austria Algorithms cluster TU Eindhoven Netherlands Technical University of Munich Germany

ISBN: (纸本)9783959773546

Boundary labeling is a technique in computational geometry used to label dense sets of feature points in an illustration. It involves placing labels along an axis-aligned bounding box and connecting each label with its corresponding feature point 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 polynomial-time algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Finally, 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. © Thomas Depian, Martin Nöllenburg, Soeren Terziadis, and Markus Wallinger.

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

FPT Approximation for Fair Minimum-Load Clustering 17

FPT Approximation for Fair Minimum-Load Clustering

引用

17th International Symposium on Parameterized and Exact Computation, IPEC 2022

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Golovach, Petr A. Purohit, Nidhi Simonov, Kirill Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772600

In this paper, we consider the Minimum-Load k-Clustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k > 0 that denotes the number of clusters. Additionally, we are given a set F of cluster centers in the same metric space. The goal is to select a set C ⊆ F of k centers and assign each point in P to a center in C, such that the maximum load over all centers is minimized. Here the load of a center is the sum of the distances between it and the points assigned to it. Although clustering/facility location problems have rich literature, the minimum-load objective has not been studied substantially, and hence MLkC has remained a poorly understood problem. More interestingly, the problem is notoriously hard even in some special cases including the one in line metrics as shown by Ahmadian et al. [APPROX 2014, ACM Trans. algorithms 2018]. They also show APX-hardness of the problem in the plane. On the other hand, the best-known approximation factor for MLkC is O(k), even in the plane. In this work, we study a fair version of MLkC inspired by the work of Chierichetti et al. [NeurIPS, 2017]. Here the input points are partitioned into protected groups, and only clusters that proportionally represent each group are allowed. MLkC is the special case with = 1. For the fair version, we are able to obtain a randomized 3-approximation algorithm in f(k, ) · nO(1) time. Also, our scheme leads to an improved (1 + ϵ)-approximation in the case of Euclidean norm with the same running time (depending also linearly on the dimension d). Our results imply the same approximations for MLkC with running time f(k) · nO(1), achieving the first constant-factor FPT approximations for this problem in general and Euclidean metric spaces. © Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit, and Kirill Simonov.

关键词： Topology

来源：评论

学校读者我要写书评

暂无评论

Self-organized transport in noisy dynamic networks

引用

Physical Review E 2024年第4期110卷 044310页

作者： Frederic Folz Kurt Mehlhorn Giovanna Morigi Theoretische Physik Algorithms and Complexity Group

We present a numerical study of multicommodity transport in a noisy, nonlinear network. The nonlinearity determines the dynamics of the edge capacities, which can be amplified or suppressed depending on the local current flowing across an edge. We consider network self-organization for three different nonlinear functions: For all three we identify parameter regimes where noise leads to self-organization into more robust topologies, that are not found by the sole noiseless dynamics. Moreover, the interplay between noise and specific functional behavior of the nonlinearity gives rise to different features, such as (i) continuous or discontinuous responses to the demand strength and (ii) either single or multistable solutions. Our study shows the crucial role of the activation function on noise-assisted phenomena.

关键词： Dynamics of networks Biological networks Stochastic dynamical systems Stochastic networks

来源：评论

学校读者我要写书评

暂无评论

Weighted Model Counting with Twin-Width 25

Weighted Model Counting with Twin-Width

引用

25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022

作者： Ganian, Robert Pokrývka, Filip Schidler, André Simonov, Kirill Szeider, Stefan Algorithms and Complexity Group TU Wien Austria Masaryk University Brno Czech Republic

ISBN: (纸本)9783959772426

Bonnet et al. (FOCS 2020) introduced the graph invariant twin-width and showed that many NP-hard problems are tractable for graphs of bounded twin-width, generalizing similar results for other width measures, including treewidth and clique-width. In this paper, we investigate the use of twin-width for solving the propositional satisfiability problem (SAT) and propositional model counting. We particularly focus on Bounded-ones Weighted Model Counting (BWMC), which takes as input a CNF formula F along with a bound k and asks for the weighted sum of all models with at most k positive literals. BWMC generalizes not only SAT but also (weighted) model counting. We develop the notion of "signed" twin-width of CNF formulas and establish that BWMC is fixed-parameter tractable when parameterized by the certified signed twin-width of F plus k. We show that this result is tight: it is neither possible to drop the bound k nor use the vanilla twin-width instead if one wishes to retain fixed-parameter tractability, even for the easier problem SAT. Our theoretical results are complemented with an empirical evaluation and comparison of signed twin-width on various classes of CNF formulas. © Robert Ganian, Filip Pokrývka, André Schidler, Kirill Simonov, and Stefan Szeider.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Parameterized complexity of Feature Selection for Categorical Data Clustering 46

Parameterized Complexity of Feature Selection for Categorica...

引用

46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Golovach, Petr A. Simonov, Kirill Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772013

We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, most of the known feature selection methods are heuristics. We study the following mathematical model. We assume that there are some inadvertent (or undesirable) features of the input data that unnecessarily increase the cost of clustering. Consequently, we want to select a subset of the original features from the data such that there is a small-cost clustering on the selected features. More precisely, for given integers (the number of irrelevant features) and k (the number of clusters), budget B, and a set of n categorical data points (represented by m-dimensional vectors whose elements belong to a finite set of values Σ), we want to select m relevant features such that the cost of any optimal k-clustering on these features does not exceed B. Here the cost of a cluster is the sum of Hamming distances (0-distances) between the selected features of the elements of the cluster and its center. The clustering cost is the total sum of the costs of the clusters. We use the framework of parameterized complexity to identify how the complexity of the problem depends on parameters k, B, and |Σ|. Our main result is an algorithm that solves the Feature Selection problem in time f(k,B, |Σ|) mg(k,|Σ|) n2 for some functions f and g. In other words, the problem is fixed-parameter tractable parameterized by B when |Σ| and k are constants. Our algorithm for Feature Selection is based on a solution to a more general problem, Constrained Clustering with Outliers. In this problem, we want to delete a certain number of outliers such that the remaining points could be clustered around centers satisfying specific constraints. One interesting fact about Constrained Clustering with Outliers is that besides Feature Selection, it encompasses many other fundamental problems r

关键词： Budget control

来源：评论

学校读者我要写书评

暂无评论

Fixed-parameter evolutionary algorithms and the vertex cover problem

Fixed-parameter evolutionary algorithms and the vertex cover...

引用

11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

作者： Kratsch, Stefan Neumann, Frank Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarbrücken Germany

ISBN: (纸本)9781605583259

In this paper, we consider multi-objective evolutionary algorithms for the Vertex Cover problem in the context of parameterized complexity. We relate the runtime of our algorithms to the input size and the cost of a minimum solution and point out that the search process of evolutionary algorithms creates partial solutions that are similar to the effect of a kernelization (i.e. a special type of preprocessing from parameterized complexity). Based on this, we show that evolutionary algorithms solve the vertex cover problem efficiently if the size of a minimum vertex cover is not too large, i.e. the expected runtime is bounded by O(f(OPT)nc), where c is a constant and f a function that only depends on OPT. This shows that evolutionary algorithms are randomized fixed-parameter tractable algorithms for the vertex cover problem. Copyright 2009 ACM.

关键词： Multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：