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

Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bartier, Valentin Defrain, Oscar Inerney, Fionn Mc Univ Lyon CNRS INSA Lyon UCBL Centrale Lyon Univ Lyon 2 LIRIS UMR5205 VilleurbanneF-69622 France Aix-Marseille Université CNRS LIS Marseille13009 France Algorithms and Complexity Group TU Wien Austria

At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an nO(d)-delay algorithm listing all minimal transversals of an n-vertex hyqpergraph of degeneracy d. Recently at IWOCA 2019, Conte, Kanté, Marino, and Uno asked whether this XP-delay algorithm parameterized by d could be made FPT-delay for a weaker notion of degeneracy, or even parameterized by the maximum degree ∆, i.e., whether it can be turned into an algorithm with delay f(∆) · nO(1) for some computable function f. Moreover, and as a first step toward answering that question, they note that they could not achieve these time bounds even for the particular case of minimal dominating sets enumeration. In this paper, using ordered generation, we show that an FPT-delay algorithm can be devised for minimal transversals enumeration parameterized by the degeneracy and dimension, giving a positive and more general answer to the latter question. © 2023, CC BY.

关键词： Parameter estimation

Towards Faster Reasoners by Using Transparent Huge Pages 26th

学校读者我要写书评

暂无评论

Towards Faster Reasoners by Using Transparent Huge Pages

26th International Conference on Principles and Practice of Constraint Programming, CP 2020

作者： Fichte, Johannes K. Manthey, Norbert Stecklina, Julian Schidler, André School of Engineering Sciences TU Dresden Dresden Germany Dresden Germany Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030584740

Various state-of-the-art automated reasoning (AR) tools are widely used as backend tools in research of knowledge representation and reasoning as well as in industrial applications. In testing and verification, those tools often run continuously or nightly. In this work, we present an approach to reduce the runtime of AR tools by 10% on average and up to 20% for long running tasks. Our improvement addresses the high memory usage that comes with the data structures used in AR tools, which are based on conflict driven no-good learning. We establish a general way to enable faster memory access by using the memory cache line of modern hardware more effectively. Therefore, we extend the standard C library (glibc) by dynamically allowing to use a memory management feature called huge pages. Huge pages allow to reduce the overhead that is required to translate memory addresses between the virtual memory of the operating system and the physical memory of the hardware. In that way, we can reduce runtime, which in turn decreases costs of running AR tools and applications with similar memory access patterns by linking the tool against this new glibc library when compiling it. In every day industrial applications, runtime savings allow to include more detailed verification tasks, getting better results of any-time optimization algorithms with a bound execution time, and save energy during nightly software builds. To back up the claimed speed-up, we present experimental results for tools that are commonly used in the AR community, including the domains ASP, hardware and software BMC, MaxSAT, and SAT. © 2020, Springer Nature Switzerland AG.

关键词： Cache memory

Worbel: Aggregating point labels into word clouds

学校读者我要写书评

暂无评论

arXiv 2021年

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

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

关键词： Visualization

Envy-free dynamic pricing schemes

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bérczi, Kristóf Codazzi, Laura Golak, Julian Grigoriev, Alexander MTA-ELTE Momentum Matroid Optimization Research Group MTA-ELTE Egerváry Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary Institute of Algorithms and Complexity Hamburg University of Technology Hamburg Germany Department of Data Analytics and Digitalisation Maastricht University Maastricht Netherlands

A combinatorial market consists of a set of indivisible items and a set of agents, where each agent has a valuation function that specifies for each subset of items its value for the given agent. From an optimization point of view, the goal is usually to determine a pair of pricing and allocation of the items that provides an efficient distribution of the resources, i.e., maximizes the social welfare, or is as profitable as possible for the seller, i.e., maximizes the revenue. To overcome the weaknesses of mechanisms operating with static prices, a recent line of research has concentrated on dynamic pricing schemes. In this model, agents arrive in an unspecified sequential order, and the prices can be updated between two agent-arrivals. Though the dynamic setting is capable of maximizing social welfare in various scenarios, the assumption that the agents arrive one after the other eliminates the standard concept of fairness. In this paper, we study the existence of optimal dynamic prices under fairness constraints in unit-demand markets. We propose four possible notions of envy-freeness of different strength depending on the time period over which agents compare themselves to others: the entire time horizon, only the past, only the future, or only the present. For social welfare maximization, while the first definition leads to Walrasian equilibria, we give polynomial-time algorithms that always find envy-free optimal dynamic prices in the remaining three cases. In contrast, for revenue maximization, we show that the corresponding problems are APX-hard if the ordering of the agents is fixed. On the positive side, we give polynomial-time algorithms for the setting when the seller can choose the order in which agents arrive. © 2023, CC BY.

关键词： Polynomial approximation

Threshold Treewidth and Hypertree Width

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Schidler, André Ganian, Robert Sorge, Manuel Szeider, Stefan Algorithms and Complexity Group Tu Wien Favoritenstrasse 9-11 Wien1040 Austria Faculty of Mathematics Informatics and Mechanics University of Warsaw ul. Banacha 2 Warsaw02-097 Poland

Treewidth and hypertree width have proven to be highly successful structural parameters in the context of the Constraint Satisfaction Problem (CSP). When either of these parameters is bounded by a constant, then CSP becomes solvable in polynomial time. However, here the order of the polynomial in the running time depends on the width, and this is known to be unavoidable;therefore, the problem is not fixed-parameter tractable parameterized by either of these width measures. Here we introduce an enhancement of tree and hypertree width through a novel notion of thresholds, allowing the associated decompositions to take into account information about the computational costs associated with solving the given CSP instance. Aside from introducing these notions, we obtain efficient theoretical as well as empirical algorithms for computing threshold treewidth and hypertree width and show that these parameters give rise to fixed-parameter algorithms for CSP as well as other, more general problems. We complement our theoretical results with experimental evaluations in terms of heuristics as well as exact methods based on SAT/SMT encodings. Copyright © 2022, The Authors. All rights reserved.

关键词： Constraint satisfaction problems

Strictly-Convex Drawings of 3-Connected Planar Graphs

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bekos, Michael A. Gronemann, Martin Montecchiani, Fabrizio Symvonis, Antonios Department of Mathematics University of Ioannina Ioannina Greece Algorithms and Complexity Group TU Wien Vienna Austria Department of Engineering University of Perugia Italy School of Applied Mathematical & Physical Sciences NTUA Greece

Strictly-convex straight-line drawings of 3-connected planar graphs in small area form a classical research topic in Graph Drawing. Currently, the best-known area bound for such drawings is O(n2)×O(n2), as shown by Bárány and Rote by means of a sophisticated technique based on perturbing (non-strictly) convex drawings. Unfortunately, the hidden constants in such area bound are in the 104 order. We present a new and easy-to-implement technique that yields strictly-convex straight-line planar drawings of 3-connected planar graphs on an integer grid of size 2(n − 1) × (5n3 − 4n2). Copyright © 2022, The Authors. All rights reserved.

关键词： Drawing (graphics)

A Time Leap Challenge for SAT-Solving 26th

学校读者我要写书评

暂无评论

A Time Leap Challenge for SAT-Solving

26th International Conference on Principles and Practice of Constraint Programming, CP 2020

作者： Fichte, Johannes K. Hecher, Markus Szeider, Stefan School of Engineering Sciences TU Dresden Dresden Germany Database and Artificial Intelligence Group TU Wien Vienna Austria Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030584740

We compare the impact of hardware advancement and algorithm advancement for SAT-solving over the last two decades. In particular, we compare 20-year-old SAT-solvers on new computer hardware with modern SAT-solvers on 20-year-old hardware. Our findings show that the progress on the algorithmic side has at least as much impact as the progress on the hardware side. © 2020, Springer Nature Switzerland AG.

关键词： Computer hardware

Noise-induced network topologies

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Folz, Frederic Mehlhorn, Kurt Morigi, Giovanna Theoretische Physik Universität des Saarlandes Saarbrücken66123 Germany Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarland Informatics Campus Saarbrücken66123 Germany

We analyze transport on a graph with multiple constraints and where the weight of the edges connecting the nodes is a dynamical variable. The network dynamics results from the interplay between a nonlinear function of the flow, dissipation, and Gaussian, additive noise. For a given set of parameters and finite noise amplitudes, the network self-organizes into one of several metastable configurations, according to a probability distribution that depends on the noise amplitude α. At a finite value α, we find a resonant-like behavior for which one network topology is the most probable stationary state. This specific topology maximizes the robustness and transport efficiency, it is reached with the maximal convergence rate, and it is not found by the noiseless dynamics. We argue that this behavior is a manifestation of noise-induced resonances in network self-organization. Our findings show that stochastic dynamics can boost transport on a nonlinear network and, further, suggest a change of paradigm about the role of noise in optimization algorithms. © 2022, CC BY-NC-SA.

关键词： Network topology

On the complexity of the Storyplan Problem

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Binucci, Carla Di Giacomo, Emilio Lenhart, William J. Liotta, Giuseppe Montecchiani, Fabrizio Nöllenburg, Martin Symvonis, Antonios Department of Engineering University of Perugia Italy Department of Computer Science Williams College United States Algorithms and Complexity Group Tu Wien Vienna Austria School of Applied Mathematical & Physical Sciences Ntua Greece

Motivated by dynamic graph visualization, we study the problem of representing a graph G in the form of a storyplan, that is, a sequence of frames with the following properties. Each frame is a planar drawing of the subgraph of G induced by a suitably defined subset of its vertices. Between two consecutive frames, a new vertex appears while some other vertices may disappear, namely those whose incident edges have already been drawn in at least one frame. In a storyplan, each vertex appears and disappears exactly once. For a vertex (edge) visible in a sequence of consecutive frames, the point (curve) representing it does not change throughout the sequence. Note that the order in which the vertices of G appear in the sequence of frames is a total order. In the StoryPlan problem, we are given a graph and we want to decide whether there exists a total order of its vertices for which a storyplan exists. We prove that the problem is NP-complete, and complement this hardness with two parameterized algorithms, one in the vertex cover number and one in the feedback edge set number of G. Also, we prove that partial 3-trees always admit a storyplan, which can be computed in linear time. Finally, we show that the problem remains NP-complete in the case in which the total order of the vertices is given as part of the input and we have to choose how to draw the frames. © 2022, CC BY.

关键词： Hardness