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

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

引用

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

引用

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

引用

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

引用

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

来源：评论

学校读者我要写书评

暂无评论

Breaking Symmetries with RootClique and LexTopSort 26th

Breaking Symmetries with RootClique and LexTopSort

引用

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

ISBN: (纸本)9783030584740

Bounded fractional hypertree width is the most general known structural property that guarantees polynomial-time solvability of the constraint satisfaction problem. Fichte et al. (CP 2018) presented a robust and scalable method for finding optimal fractional hypertree decompositions, based on an encoding to SAT Modulo Theory (SMT). In this paper, we provide an in-depth study of two powerful symmetry breaking predicates that allow us to further speed up the SMT-based decomposition: RootClique fixes the root of the decomposition tree;LexTopSort fixes the elimination ordering with respect to an underlying DAG. We perform an extensive empirical evaluation of both symmetry-breaking predicates with respect to the primal graph (which is known in advance) and the induced graph (which is generated during the search). © 2020, Springer Nature Switzerland AG.

关键词： Constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Longest Cycle above Erdos–Gallai Bound

arXiv

引用

arXiv 2022年

作者： Fomin, Fedor V. Golovach, Petr A. Simonov, Kirill Sagunov, Danil Department of Informatics University of Bergen Norway St. Petersburg Department of V.A. Steklov Institute of Mathematics Russia JetBrains Research Saint Petersburg Russia Algorithms and Complexity Group TU Wien Austria

In 1959, Erdos and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2O(k) · nO(1) decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G) + k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own. © 2022, CC BY.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Independent sets of dynamic rectangles: algorithms and experiments

arXiv

引用

arXiv 2020年

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

We study the maximal independent set (MIS) and maximum independent set (Max-IS) problems on dynamic sets of O(n) axis-parallel rectangles, which can be modeled as dynamic rectangle intersection graphs. We consider the fully dynamic vertex update (insertion/deletion) model for two types of rectangles: (i) uniform height and width and (ii) uniform height and arbitrary width. These types of dynamic vertex update problems arise, e.g., in interactive map labeling. We present the first deterministic algorithm for maintaining a MIS (and thus a 4-approximate Max-IS) of a dynamic set of uniform rectangles with amortized sub-logarithmic update time. This breaks the natural barrier of O(Δ) update time (where Δ is the maximum degree in the graph) for vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating Max-IS and provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first give an algorithm that maintains a 4-approximate Max-IS with O(1) update time. In a subsequent algorithm, we establish the trade-off between approximation quality 2(1 + 1/k) and update time O(k2log n) for k ∈ . We conclude with an algorithm that maintains a 2-approximate Max-IS for dynamic sets of uniform height and arbitrary width rectangles with O(ω log n) update time, where ω is the largest number of maximal cliques stabbed by any axis-parallel line. We have implemented our algorithms and report the results of an experimental comparison exploring the trade-off between solution size and update time for synthetic and real-world map labeling data sets. Copyright © 2020, The Authors. All rights reserved.

关键词： Geometry

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：