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

arXiv 2023年

作者： Chalopin, Jérémie Chepoi, Victor Mc Inerney, Fionn Ratel, Sébastien Aix-Marseille Université Université de Toulon CNRS LIS Marseille France Algorithms and Complexity Group TU Wien Vienna Austria

Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and showed it to be the most efficient machine teaching model satisfying the benchmark for collusion-avoidance set by Goldman and Mathias. A teaching map T for a concept class C assigns a (teaching) set T(C) of examples to each concept C ∈ C. A teaching map is non-clashing if no pair of concepts are consistent with the union of their teaching sets. The size of a non-clashing teaching map (NCTM) T is the maximum size of a teaching set T(C), C ∈ C. The non-clashing teaching dimension NCTD(C) of C is the minimum size of an NCTM for C. NCTM+ and NCTD+(C) are defined analogously, except the teacher may only use positive examples. We study NCTMs and NCTM+s for the concept class B(G) consisting of all balls of a graph G. We show that the associated decision problem B-NCTD+ for NCTD+ is NP-complete in split, co-bipartite, and bipartite graphs. Surprisingly, we even prove that, unless the ETH fails, B-NCTD+ does not admit an algorithm running in time 22o(vc) · nO(1), nor a kernelization algorithm outputting a kernel with 2o(vc) vertices, where vc is the vertex cover number of G. We complement these lower bounds with matching upper bounds. These are extremely rare results: it is only the second problem in NP to admit such a tight double-exponential lower bound parameterized by vc, and only one of very few problems to admit such an ETH-based conditional lower bound on the number of vertices in a kernel. For trees, interval graphs, cycles, and trees of cycles, we derive NCTM+s or NCTMs for B(G) of size proportional to its VC-dimension. For Gromov-hyperbolic graphs, we design an approximate NCTM+ for B(G) of size 2, in which only pairs of balls with Hausdorff distance larger than some constant must satisfy the non-clashing condition. Copyright © 2023, The Authors. All rights reserved.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

An algorithmic study of fully dynamic independent sets for map labeling 28

An algorithmic study of fully dynamic independent sets for m...

引用

28th Annual European Symposium on algorithms, ESA 2020

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

ISBN: (纸本)9783959771627

Map labeling is a classical problem in cartography and geographic information systems (GIS) that asks to place labels for area, line, and point features, with the goal to select and place the maximum number of independent, i.e., overlap-free, labels. A practically interesting case is point labeling with axis-parallel rectangular labels of common size. In a fully dynamic setting, at each time step, either a new label appears or an existing label disappears. Then, the challenge is to maintain a maximum cardinality subset of pairwise independent labels with sub-linear update time. Motivated by this, we study the maximal independent set (MIS) and maximum independent set (Max-IS) problems on fully dynamic (insertion/deletion model) sets of axis-parallel rectangles of two types – (i) uniform height and width and (ii) uniform height and arbitrary width;both settings can be modeled as rectangle intersection graphs. 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 Ω(∆) 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 + k1 ) and update time O(k2 log n), for k ∈ N. We conclude with an algorithm that maintains a 2-approximate Max-IS for dynamic sets of unit-height and arbitrary-width rectangles with O(ω log n) update time, where ω is the maximum size of an independent set of rectangles stabbed by any horizontal line. We have implemented our algorithms and report the results of an experimental comparison exploring the trade-off between solution qu

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Weighted Model Counting with Twin-Width

arXiv

引用

arXiv 2022年

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

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

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Transitions in Dynamic Point Labeling

arXiv

引用

arXiv 2022年

作者： Depian, Thomas Li, Guangping Nöllenburg, Martin Wulms, Jules Algorithms and Complexity Group TU Wien Vienna Austria Algorithm Engineering Group TU Dortmund Dortmund Germany

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. Copyright © 2022, The Authors. All rights reserved.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Noise-Induced Network Topologies

引用

Physical Review Letters 2023年第26期130卷 267401-267401页

作者： Frederic Folz Kurt Mehlhorn Giovanna Morigi Theoretische Physik Universität des Saarlandes 66123 Saarbrücken Germany Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarland Informatics Campus 66123 Saarbrücken 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 resonantlike 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.

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

The complexity of Bayesian network learning: revisiting the superstructure 21

The complexity of Bayesian network learning: revisiting the ...

引用

Proceedings of the 35th International Conference on Neural Information Processing Systems

作者： Robert Ganian Viktoriia Korchemna Algorithms and Complexity Group TU Wien

ISBN: (纸本)9781713845393

We investigate the parameterized complexity of Bayesian Network Structure Learning (BNSL), a classical problem that has received significant attention in empirical but also purely theoretical studies. We follow up on previous works that have analyzed the complexity of BNSL w.r.t. the so-called superstructure of the input. While known results imply that BNSL is unlikely to be fixed-parameter tractable even when parameterized by the size of a vertex cover in the superstructure, here we show that a different kind of parameterization—notably by the size of a feedback edge set—yields fixed-parameter tractability. We proceed by showing that this result can be strengthened to a localized version of the feedback edge set, and provide corresponding lower bounds that complement previous results to provide a complexity classification of BNSL w.r.t. virtually all well-studied graph *** then analyze how the complexity of BNSL depends on the representation of the input. In particular, while the bulk of past theoretical work on the topic assumed the use of the so-called non-zero representation, here we prove that if an additive representation can be used instead then BNSL becomes fixed-parameter tractable even under significantly milder restrictions to the superstructure, notably when parameterized by the treewidth alone. Last but not least, we show how our results can be extended to the closely related problem of Polytree Learning.

关键词：

来源：评论

学校读者我要写书评

暂无评论

MaxSAT-Based Postprocessing for Treedepth 26th

MaxSAT-Based Postprocessing for Treedepth

引用

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

作者： Peruvemba Ramaswamy, Vaidyanathan Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030584740

Treedepth is an increasingly popular graph invariant. Many NP-hard combinatorial problems can be solved efficiently on graphs of bounded treedepth. Since the exact computation of treedepth is itself NP-hard, recent research has focused on the development of heuristics that compute good upper bounds on the treedepth. In this paper, we introduce a novel MaxSAT-based approach for improving a heuristically obtained treedepth decomposition. At the core of our approach is an efficient MaxSAT encoding of a weighted generalization of treedepth arising naturally due to subtree contractions. The encoding is applied locally to the given treedepth decomposition to reduce its depth, in conjunction with the collapsing of subtrees. We show the local improvement method’s correctness and provide an extensive experimental evaluation with some encouraging results. © 2020, Springer Nature Switzerland AG.

关键词： Forestry

来源：评论

学校读者我要写书评

暂无评论

Skipping the Crowds: Cognitive Impact of Real-Time On-Board Crowding Information in Mass Transit Smartphone Mobility Apps

SSRN

引用

SSRN 2024年

作者： Prabhakar, Archana Grison, Elise Morgagni, Simone Nöllenburg, Martin Gyselinck, Valérie SNCF Research Department La Plaine Saint-Denis France Université Gustave Eiffel Université Paris Cité Versailles France Algorithms and Complexity Group TU Wien Vienna Austria

Dense mass transit systems are prone to suboptimal exploitation of their infrastructure when passenger congestion concentrates on specific routes, leaving alternative routes underused. This imbalance may arise from passengers relying on a cognitive heuristic to find the fastest path without considering other parameters, partly for lack of information. Providing on-board crowding information via smartphone mobility apps before boarding could increase their willingness-to-wait for a less crowded route. An online experimental paradigm was designed to investigate how individuals evaluate different combinations of crowding levels, waiting times, and in-vehicle times when selecting routes for non-time-sensitive trips in the Parisian mass transit which is unfamiliar to them. We aimed to simulate the dynamic nature of passengers' decision-making processes and provide insights into the cognitive mechanisms underlying real-world decisions. Results indicate that the participants showed greater willingness-to-wait for less crowded alternatives, especially when the default route was highly crowded, and the alternative route lightly crowded. Short waiting times and long in-vehicle times also increased willingness-to-wait. Thus, our findings confirm that the availability of crowding information in smartphone mobility apps during route planning can effectively regulate passenger flow in mass transit. This lever lowers passengers’ reliance on a cognitive heuristic to find the fastest route, guiding them towards less crowded alternatives. © 2024, The Authors. All rights reserved.

关键词： Travel time

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：