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

40th International Symposium on Computational Geometry, SoCG 2024

作者： Bhore, Sujoy Nöllenburg, Martin Tóth, Csaba D. Wulms, Jules Department of Computer Science and Engineering Indian Institute of Technology Bombay Mumbai India Institute of Logic and Computation Algorithms and Complexity Group TU Wien Austria Department of Mathematics California State University Northridge Los AngelesCA United States Department of Computer Science Tufts University MedfordMA United States Department of Mathematics and Computer Science TU Eindhoven Netherlands

ISBN: (纸本)9783959773164

A fundamental question is whether one can maintain a maximum independent set (MIS) in polylogarithmic update time for a dynamic collection of geometric objects in Euclidean space. For a set of intervals, it is known that no dynamic algorithm can maintain an exact MIS in sublinear update time. Therefore, the typical objective is to explore the trade-off between update time and solution size. Substantial efforts have been made in recent years to understand this question for various families of geometric objects, such as intervals, hypercubes, hyperrectangles, and fat objects. We present the first fully dynamic approximation algorithm for disks of arbitrary radii in the plane that maintains a constant-factor approximate MIS in polylogarithmic expected amortized update time. Moreover, for a fully dynamic set of n unit disks in the plane, we show that a 12-approximate MIS can be maintained with worst-case update time O(log n), and optimal output-sensitive reporting. This result generalizes to fat objects of comparable sizes in any fixed dimension d, where the approximation ratio depends on the dimension and the fatness parameter. Further, we note that, even for a dynamic set of disks of unit radius in the plane, it is impossible to maintain O(1 + Ε)-approximate MIS in truly sublinear update time, under standard complexity assumptions. Our results build on two recent technical tools: (i) The MIX algorithm by Cardinal et al. (ESA 2021) that can smoothly transition from one independent set to another;hence it suffices to maintain a family of independent sets where the largest one is an O(1)-approximate MIS. (ii) A dynamic nearest/farthest neighbor data structure for disks by Kaplan et al. (DCG 2020) and Liu (SICOMP 2022), which generalizes the dynamic convex hull data structure by Chan (JACM 2010), and quickly yields a "replacement" disk (if any) when a disk in one of our independent sets is deleted. © Sujoy Bhore, Martin Nöllenburg, Csaba D. Tóth, and Jules Wulms.

关键词： Data structures

来源：评论

学校读者我要写书评

暂无评论

Worbel: Aggregating Point Labels into Word Clouds 21

Worbel: Aggregating Point Labels into Word Clouds

引用

29th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL 2021

作者： Bhore, Sujoy Ganian, Robert Li, Guangping Nöllenburg, Martin Wulms, Jules Indian Institute of Science Education and Research Bhopal Bhopal India Algorithms and Complexity Group Tu Wien Vienna Austria

ISBN: (纸本)9781450386647

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster. © 2021 ACM.

关键词： Visualization

来源：评论

学校读者我要写书评

暂无评论

The k-Opt algorithm for the Traveling Salesman Problem has exponential running time for k ≥ 5

arXiv

引用

arXiv 2024年

作者： Heimann, Sophia Hoang, Hung P. Hougardy, Stefan Research Institute for Discrete Mathematics University of Bonn Germany Algorithms and Complexity Group Faculty of Informatics TU Wien Austria Research Institute for Discrete Mathematics and Hausdorff Center for Mathematics University of Bonn Germany

The k-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most k edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the k-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the k-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires k 1000 and has a substantial gap. We show the two properties above for a much smaller value of k, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for k ≥ 17 and the exponential running time for k ≥ *** Codes 68W25, 68W40, 68Q25, 90C27 © 2024, CC BY-NC-ND.

关键词： Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

Clustered Planarity Variants for Level Graphs

arXiv

引用

arXiv 2024年

作者： Fink, Simon D. Pfretzschner, Matthias Rutter, Ignaz Sieper, Marie Diana Algorithms and Complexity Group Technische Universität Wien Austria Faculty of Computer Science and Mathematics University of Passau Germany Institute of Computer Science University of Würzburg Germany

We consider variants of the clustered planarity problem for level-planar drawings. So far, only convex clusters have been studied in this setting. We introduce two new variants that both insist on a level-planar drawing of the input graph but relax the requirements on the shape of the clusters. In unrestricted Clustered Level Planarity (uCLP) we only require that they are bounded by simple closed curves that enclose exactly the vertices of the cluster and cross each edge of the graph at most once. The problem y-monotone Clustered Level Planarity (y-CLP) requires that additionally it must be possible to augment each cluster with edges that do not cross the cluster boundaries so that it becomes connected while the graph remains level-planar, thereby mimicking a classic characterization of clustered planarity in the level-planar setting. We give a polynomial-time algorithm for uCLP if the input graph is biconnected and has a single source. By contrast, we show that y-CLP is hard under the same restrictions and it remains NP-hard even if the number of levels is bounded by a constant and there is only a single non-trivial cluster. © 2024, CC BY.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

IMPARTIAL SELECTION UNDER COMBINATORIAL CONSTRAINTS

arXiv

引用

arXiv 2024年

作者： Cembrano, Javier Klimm, Max Merino, Arturo Department of Algorithms and Complexity Max Planck Institut für Informatik Germany Institute for Mathematics Technische Universität Berlin Germany Institute of Engineering Sciences Universidad de O'Higgins Chile

Impartial selection problems are concerned with the selection of one or more agents from a set based on mutual nominations from within the set. To avoid strategic nominations of the agents, the axiom of impartiality requires that the selection of each agent is independent of the nominations cast by that agent. This paper initiates the study of impartial selection problems where the nominations are weighted and the set of agents that can be selected is restricted by a combinatorial constraint. We call a selection mechanism α-optimal if, for every instance, the ratio between the total sum of weighted nominations of the selected set and that of the best feasible set of agents is at least α. We show that a natural extension of a mechanism studied for the selection of a single agent remains impartial and 1/4-optimal for general independence systems, and we generalize upper bounds from the selection of multiple agents by parameterizing them by the girth of the independence system. We then focus on independence systems defined by knapsack and matroid constraints, giving impartial mechanisms that exploit a greedy order of the agents and achieve approximation ratios of 1/3 and 1/2, respectively, when agents cast a single nomination. For graphic matroids, we further devise an impartial and 1/3-optimal mechanism for an arbitrary number of unweighted nominations. Copyright © 2024, The Authors. All rights reserved.

关键词： Optimal systems

来源：评论

学校读者我要写书评

暂无评论

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates

arXiv

引用

arXiv 2024年

作者： Kaul, Matthias Mnich, Matthias Molter, Hendrik Universität Bonn Germany Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Department of Computer Science Ben-Gurion University of the Negev Be’er-Sheva Israel

We study the fundamental scheduling problem 1 | rj | P wjUj: schedule a set of n jobs with weights, processing times, release dates, and due dates on a single machine, such that each job starts after its release date and we maximize the weighted number of jobs that complete execution before their due date. Problem 1 | rj | P wjUj generalizes both Knapsack and Partition, and the simplified setting without release dates was studied by Hermelin et al. [Annals of Operations Research, 2021] from a parameterized complexity viewpoint. Our main contribution is a thorough complexity analysis of 1 | rj | P wjUj in terms of four key problem parameters: the number p# of processing times, the number w# of weights, the number d# of due dates, and the number r# of release dates of the jobs. 1 | rj | P wjUj is known to be weakly para-NP-hard even if w# + d# + r# is constant, and Heeger and Hermelin [ESA, 2024] recently showed (weak) W[1]-hardness parameterized by p# or w# even if r# is constant. Algorithmically, we show that 1 | rj | P wjUj is fixed-parameter tractable parameterized by p# combined with any two of the remaining three parameters w#, d#, and r#. We further provide pseudo-polynomial XP-time algorithms for parameter r# and d#. To complement these algorithms, we show that 1 | rj | P wjUj is (strongly) W[1]-hard when parameterized by d# + r# even if w# is constant. Our results provide a nearly complete picture of the complexity of 1 | rj | P wjUj for p#, w#, d#, and r# as parameters, and extend those of Hermelin et al. [Annals of Operations Research, 2021] for the problem 1 || P wjUj without release dates. Copyright © 2024, The Authors. All rights reserved.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Enumerating minimal solution sets for metric graph problems

arXiv

引用

arXiv 2023年

作者： Bergougnoux, Benjamin Defrain, Oscar Inerney, Fionn Mc Institute of Informatics University of Warsaw Poland LIS Aix-Marseille Université France Algorithms and Complexity Group Technische Universität Wien Austria

Problems from metric graph theory like Metric Dimension, Geodetic Set, and Strong Metric Dimension have recently had a strong impact in parameterized complexity by being the first known problems in NP to admit double-exponential lower bounds in the treewidth, and even in the vertex cover number for the latter, assuming the Exponential Time Hypothesis. We initiate the study of enumerating minimal solution sets for these problems and show that they are also of great interest in enumeration. Specifically, we show that enumerating minimal resolving sets in graphs and minimal geodetic sets in split graphs are equivalent to enumerating minimal transversals in hypergraphs (denoted Trans-Enum), whose solvability in total-polynomial time is one of the most important open problems in algorithmic enumeration. This provides two new natural examples to a question that emerged in recent works: for which vertex (or edge) set graph property Π is the enumeration of minimal (or maximal) subsets satisfying Π equivalent to Trans-Enum? As very few properties are known to fit within this context—namely, those related to minimal domination—our results make significant progress in characterizing such properties, and provide new angles to approach Trans-Enum. In contrast, we observe that minimal strong resolving sets can be enumerated with polynomial delay. Additionally, we consider cases where our reductions do not apply, namely graphs with no long induced paths, and show both positive and negative results related to the enumeration and extension of partial solutions. © 2023, CC BY.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

No Polynomial Kernels for Knapsack

arXiv

引用

arXiv 2023年

作者： Heeger, Klaus Hermelin, Danny Mnich, Matthias Shabtay, Dvir Department of Industrial Engineering and Management Ben-Gurion University of the Negev Beer-Sheva Israel Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany

This paper focuses on kernelization algorithms for the fundamental Knapsack problem. A kernelization algorithm (or kernel) is a polynomial-time reduction from a problem onto itself, where the output size is bounded by a function of some problem-specific parameter. Such algorithms provide a theoretical model for data reduction and preprocessing and are central in the area of parameterized complexity. In this way, a kernel for Knapsack for some parameter k reduces any instance of Knapsack to an equivalent instance of size at most f(k) in polynomial time, for some computable function f(·). When f(k) = kO(1) then we call such a reduction a polynomial kernel. Our study focuses on two natural parameters for Knapsack: The number of different item weights w#, and the number of different item profits p#. Our main technical contribution is a proof showing that Knapsack does not admit a polynomial kernel for any of these two parameters under standard complexity-theoretic assumptions. Our proof discovers an elaborate application of the standard kernelization lower bound framework, and develops along the way novel ideas that should be useful for other problems as well. We complement our lower bounds by showing the Knapsack admits a polynomial kernel for the combined parameter w# + p# Copyright © 2023, The Authors. All rights reserved.

关键词： Profitability

来源：评论

学校读者我要写书评

暂无评论

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

arXiv

引用

arXiv 2023年

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

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 coefficient in any constraint. Our main combinatorial result are improved support size bounds for ILPs. To improve granularity, we analyze for the largest 1-norm Amax of any column of the constraint matrix, instead of ∆. We show a support size upper bound of s ≤ m · (log(3Amax) + √log(Amax)), by deriving a new bound on the -1 branch of the Lambert W function. Additionally, we provide a lower bound of mlog(Amax), proving our result asymptotically optimal. Furthermore, we give support bounds of the form s ≤ 2m · log(1.46Amax). These improve upon the previously best constants by Aliev. et. al. (SIAM J. Optim. 2018), because all our upper bounds hold equally with Amax replaced by √m∆. Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. First, 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. Second, we consider Q|HM|Cma

关键词： Integer programming

来源：评论

学校读者我要写书评

暂无评论

Learning Depth Vision-Based Personalized Robot Navigation From Dynamic Demonstrations in Virtual Reality

arXiv

引用

arXiv 2022年

作者： de Heuvel, Jorge Corral, Nathan Kreis, Benedikt Conradi, Jacobus Driemel, Anne Bennewitz, Maren Group for Algorithms and Complexity University of Bonn Germany Lamarr Institute for Machine Learning and Artificial Intelligence Germany

— For the best human-robot interaction experience, the robot’s navigation policy should take into account personal preferences of the user. In this paper, we present a learning framework complemented by a perception pipeline to train a depth vision-based, personalized navigation controller from user demonstrations. Our virtual reality interface enables the demonstration of robot navigation trajectories under motion of the user for dynamic interaction scenarios. The novel perception pipeline enrolls a variational autoencoder in combination with a motion predictor. It compresses the perceived depth images to a latent state representation to enable efficient reasoning of the learning agent about the robot’s dynamic environment. In a detailed analysis and ablation study, we evaluate different configurations of the perception pipeline. To further quantify the navigation controller’s quality of personalization, we develop and apply a novel metric to measure preference reflection based on the Fréchet Distance. We discuss the robot’s navigation performance in various virtual scenes and demonstrate the first personalized robot navigation controller that solely relies on depth images. A supplemental video highlighting our approach is available online1 Copyright © 2022, The Authors. All rights reserved.

关键词： Demonstrations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：