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

International MultiConference of Engineers and Computer Scientists, IMECS 2014

作者： Clemente, Jhoirene B. Aborot, Jeffrey A. Adorna, Henry N. Algorithms and Complexity Lab Department of Computer Science University of the Philippines Diliman Philippines

ISBN: (纸本)9789881925251

One of the approaches in solving NP-hard problems is through reoptimization. In this technique, we solve a locally modified instance of a problem by making use of known solution to its original instance instead of obtaining a solution from scratch. In this paper, we present a reoptimization of motif finding problem. Since the problem is showed to be self-reducible, we can use a self-reduction method to solve the reoptimization variant of the problem. Using the method, we have improved the approximation ratio of the algorithm solving the reoptimized version as compared to the non-reoptimized counterpart. Moreover, we showed that if a certain problem is self-reducible, any problem that obtains a polynomial-time reduction to it is also self-reducible.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

The Parameterized complexity of Coordinated Motion Planning 39

The Parameterized Complexity of Coordinated Motion Planning

引用

39th International Symposium on Computational Geometry, SoCG 2023

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Austria School of Computing DePaul University ChicagoIL United States

ISBN: (纸本)9783959772730

In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the k robots to their destinations which minimizes a certain objective target - prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former objective target as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous (n2 − 1)-puzzle as a special case. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish - as a simpler case - the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids. © Eduard Eiben, Robert Ganian, and Iyad Kanj;licensed under Creative Commons License CC-BY 4.0.

关键词： Motion planning

来源：评论

学校读者我要写书评

暂无评论

On the Upward Book Thickness Problem: Combinatorial and complexity Results 29th

On the Upward Book Thickness Problem: Combinatorial and Com...

引用

29th International Symposium on Graph Drawing and Network Visualization, GD 2021

作者： Bhore, Sujoy Da Lozzo, Giordano Montecchiani, Fabrizio Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Roma Tre University Rome Italy Department of Engineering University of Perugia Perugia Italy Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030929305

A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are st-outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness k is NP-hard for any fixed k≥ 3. We show that the problem, for any k≥ 5, remains NP-hard for graphs whose domination number is O(k), but it is FPT in the vertex cover number. © 2021, Springer Nature Switzerland AG.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

The Parameterized complexity of Network Microaggregation 37

The Parameterized Complexity of Network Microaggregation

引用

37th AAAI Conference on Artificial Intelligence, AAAI 2023

作者： Blažej, Václav Ganian, Robert Knop, Dušan Pokorný, Jan Schierreich, Šimon Simonov, Kirill Faculty of Information Technology Czech Technical University in Prague Prague Czech Republic Algorithms and Complexity Group Technische Universität Wien Vienna Austria Hasso Plattner Institute University of Potsdam Postdam Germany

ISBN: (纸本)9781577358800

Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network. Copyright © 2023, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Communication complexity and lower bounds on multilective computations

Theoretical Informatics and Applications

引用

Theoretical Informatics and Applications 1999年第2期33卷 193-212页

作者： Hromkovič, Juraj Department of Computer Science I Algorithms and Complexity University of Technology Aachen Ahornstrasse 55 52056 Aachen Germany

A general framework for the use of two-party communication protocols for lower bound proofs on multilective computations was developed. The result not only created a transparent presentation of some known lower bounds on the complexity of multilective computations on distinct computing models but also the derivation of new nontrivial lower bounds on multilective VLSI circuits and multilective planar Boolean circuits. Another advantage of this framework is that it provides lower bounds for a lot of concrete functions.

关键词： Boolean functions

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

The complexity landscape of decompositional parameters for ILP

arXiv

引用

arXiv 2018年

作者： Ganian, Robert Ordyniak, Sebastian Algorithms and Complexity Group TU Wien Favoritenstrasse 9-11 Wien1040 Austria

Integer Linear Programming (ILP) can be seen as the archetypical problem for NP-complete optimization problems, and a wide range of problems in artificial intelligence are solved in practice via a translation to ILP. Despite its huge range of applications, only few tractable fragments of ILP are known, probably the most prominent of which is based on the notion of total unimodularity. Using entirely different techniques, we identify new tractable fragments of ILP by studying structural parameterizations of the constraint matrix within the framework of parameterized complexity. In particular, we show that ILP is fixed-parameter tractable when parameterized by the treedepth of the constraint matrix and the maximum absolute value of any coefficient occurring in the ILP instance. Together with matching hardness results for the more general parameter treewidth, we give an overview of the complexity of ILP w.r.t. decompositional parameters defined on the constraint matrix. Copyright © 2018, The Authors. All rights reserved.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：