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

DISCRETE & COMPUTATIONAL GEOMETRY 2024年第4期71卷 1456-1506页

作者： Alkema, Henk de Berg, Mark van der Hofstad, Remco Kisfaludi-Bak, Sandor TU Eindhoven Dept Math & Comp Sci Eindhoven Netherlands Aalto Univ Espoo Finland

We investigate how the complexity of Euclidean TSP for point sets P inside the strip (-infinity,+infinity)x[0,delta] depends on the strip width delta . - We obtain two main *** the case where the points have distinct integer -coordinates, we prove that a shortest bitonic tour (which can be computed in O(nlog(2)n) time using an existing algorithm) is guaranteed to be a shortest tour overall when delta <= 2 root 2 , a bound which is best possible. - We present an algorithm that is fixed-parameter tractable with respect to delta . Our algorithm has running time 2(O(root delta)n)+O(delta(2)n(2)) for sparse point sets, where each 1x delta rectangle inside the strip contains (1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [0,n]x[0,delta] , it has an expected running time of 2(O(root delta)n) . These results generalise to point sets inside a hypercylinder of width delta . In this case, the factors 2(O(root delta)) become 2(O(delta 1-1/d)) .

关键词： Computational geometry Euclidean TSP Bitonic TSP fixed-parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

Infrared: a declarative tree decomposition-powered framework for bioinformatics

引用

algorithms FOR MOLECULAR BIOLOGY 2024年第1期19卷 13页

作者： Yao, Hua-Ting Marchand, Bertrand Berkemer, Sarah J. Ponty, Yann Will, Sebastian Ecole Polytech CNRS Inst Polytech Paris LIXUMR 7161 Palaiseau France Univ Vienna Dept Theoret Chem Vienna Austria McGill Univ Sch Comp Sci Montreal PQ Canada Tokyo Inst Technol Earth Life Sci Inst Tokyo Japan

MotivationMany bioinformatics problems can be approached as optimization or controlled sampling tasks, and solved exactly and efficiently using Dynamic Programming (DP). However, such exact methods are typically tailored towards specific settings, complex to develop, and hard to implement and adapt to problem *** introduce the Infrared framework to overcome such hindrances for a large class of problems. Its underlying paradigm is tailored toward problems that can be declaratively formalized as sparse feature networks, a generalization of constraint networks. Classic Boolean constraints specify a search space, consisting of putative solutions whose evaluation is performed through a combination of features. Problems are then solved using generic cluster tree elimination algorithms over a tree decomposition of the feature network. Their overall complexities are linear on the number of variables, and only exponential in the treewidth of the feature network. For sparse feature networks, associated with low to moderate treewidths, these algorithms allow to find optimal solutions, or generate controlled samples, with practical empirical *** these methods, the Infrared software allows Python programmers to rapidly develop exact optimization and sampling applications based on a tree decomposition-based efficient processing. Instead of directly coding specialized algorithms, problems are declaratively modeled as sets of variables over finite domains, whose dependencies are captured by constraints and functions. Such models are then automatically solved by generic DP algorithms. To illustrate the applicability of Infrared in bioinformatics and guide new users, we model and discuss variants of bioinformatics applications. We provide reimplementations and extensions of methods for RNA design, RNA sequence-structure alignment, parsimony-driven inference of ancestral traits in phylogenetic trees/networks, and design of coding sequences.

关键词： Bioinformatics fixed-parameter tractable algorithms Tree decomposition Boltzmann sampling Network phylogeny RNA sequence design RNA alignment Pseudoknots

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for multi-module capacitated lot-sizing problem, and its generalizations with two-echelons and piecewise concave production costs

引用

IISE TRANSACTIONS 2023年第12期55卷 1187-1202页

作者： Kulkarni, Kartik Bansal, Manish Virginia Tech Grad Dept Ind & Syst Engn Blacksburg VA 24061 USA

We study new generalizations of the classic capacitated lot-sizing problem with concave production (or transportation), holding, and subcontracting cost functions in which the total production (or transportation) capacity in each time period is the summation of capacities of a subset of n available modules (machines or vehicles) of different capacities. We refer to this problem as Multi-module Capacitated Lot-Sizing Problem without or with Subcontracting, and denote it by MCLS or MCLS-S, respectively. These are NP-hard problems if n is a part of the input and polynomially solvable for n = 1. In this article we address an open question: Does there exist a polynomial time exact algorithm for solving the MCLS or MCLS-S with fixed n >= 2? We present exact fixed-parameter tractable (polyno-mial) algorithms that solve MCLS and MCLS-S in O(T2n+3) time for a given n > 2: It generalizes algo-rithm of Atamtu euro rk and Hochbaum [Management Science 47(8):1081-1100, 2001] for MCLS-S with n = 1. We also present exact algorithms for two-generalizations of the MCLS and MCLS-S: (a) a lot-siz-ing problem with piecewise concave production cost functions (denoted by LS-PC-S) that takes O(T2m+3) time, where m is the number of breakpoints in these functions, and (b) two-echelon MCLS that takes O(T4n+4) time. The former reduces run time of algorithm of Koca et al. [INFORMS J. on Computing 26(4):767-779, 2014] for LS-PC-S by 93.6%, and the latter generalizes algorithm of van Hoesel et al. [Management Science 51(11):1706-1719, 2005] for two-echelon MCLS with n =1. We per-form computational experiments to evaluate the efficiency of our algorithms for MCLS and LS-PC-S and their parallel computing implementation, in comparison to Gurobi 9.1. The results of these experi-ments show that our algorithms are computationally efficient and stable. Our algorithm for MCLS-S addresses another open question related to the existence of a polynomial time algorithm for optimiz-ing a linear function over n

关键词： Multi-module capacitated lot-sizing piecewise concave production cost two-echelon capacitated lot-sizing multi-mode lot-sizing n-mixing set fixed-parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

Diverse Collections in Matroids and Graphs 38

Diverse Collections in Matroids and Graphs

引用

38th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Fomin, Fedor, V Golovach, Petr A. Panolan, Fahad Philip, Geevarghese Saurabh, Saket Univ Bergen Bergen Norway IIT Hyderabad Dept Comp Sci & Engn Hyderabad India Chennai Math Inst Chennai Tamil Nadu India UMI ReLaX Chennai Tamil Nadu India Inst Math Sci4 Chennai Tamil Nadu India

ISBN: (纸本)9783959771801

We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the WEIGHTED DIVERSE BASES problem consists of a matroid M, a weight function omega : E(M) -> N, and integers k >= 1, d >= 0. The task is to decide if there is a collection of k bases B-1, ... , B-k of M such that the weight of the symmetric difference of any pair of these bases is at least d. This is a diverse variant of the classical matroid base packing problem. The input to the WEIGHTED DIVERSE COMMON INDEPENDENT SETS problem consists of two matroids M-1, M-2 defined on the same ground set E, a weight function omega : E -> N, and integers k >= 1, d >= 0. The task is to decide if there is a collection of k common independent sets I-1, ... , I-k of M-1 and M-2 such that the weight of the symmetric difference of any pair of these sets is at least d. This is motivated by the classical weighted matroid intersection problem. The input to the DIVERSE PERFECT MATCHINGS problem consists of a graph G and integers k >= 1, d >= 0. The task is to decide if G contains k perfect matchings M-1, ... , M-k such that the symmetric difference of any two of these matchings is at least d. The underlying problem of finding one solution (basis, common independent set, or perfect matching) is known to be doable in polynomial time for each of these problems, and DIVERSE PERFECT MATCHINGS is known to be NP-hard for k = 2. We show that WEIGHTED DIVERSE BASES and WEIGHTED DIVERSE COMMON INDEPENDENT SETS are both NP-hard. We show also that DIVERSE PERFECT MATCHINGS cannot be solved in polynomial time (unless P = NP) even for the case d = 1. We derive fixed-parameter tractable (FPT) algorithms for all three problems with (k, d) as the parameter. The above results on matroids are derived under the assumption that the input matroids are given as independence oracles. For WEIGHTED DIVERSE BASES

关键词： Matroids Diverse solutions fixed-parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving hard stable matching problems involving groups of similar agents

引用

THEORETICAL COMPUTER SCIENCE 2020年 844卷 171-194页

作者： Meeks, Kitty Rastegari, Baharak Univ Glasgow Sch Comp Sci Glasgow Lanark Scotland Univ Southampton Dept Elect & Comp Sci Southampton Hants England

Many important stable matching problems are known to be NP-hard, even when strong restrictions are placed on the input. In this paper we seek to identify structural properties of instances of stable matching problems which will allow us to design efficient algorithms using elementary techniques. We focus on the setting in which all agents involved in some matching problem can be partitioned into k different types, where the type of an agent determines his or her preferences, and agents have preferences over types (which may be refined by more detailed preferences within a single type). This situation would arise in practice if agents form preferences solely based on some small collection of agents' attributes. We also consider a generalisation in which each agent may consider some small collection of other agents to be exceptional, and rank these in a way that is not consistent with their types;this could happen in practice if agents have prior contact with a small number of candidates. We show that (for the case without exceptions), several well-studied NP-hard stable matching problems including MAX SMTI (that of finding the maximum cardinality stable matching in an instance of stable marriage with ties and incomplete lists) belong to the parameterised complexity class FPT when parameterised by the number of different types of agents needed to describe the instance. For MAX SMTI this tractability result can be extended to the setting in which each agent promotes at most one "exceptional" candidate to the top of his/her list (when preferences within types are not refined), but the problem remains NP-hard if preference lists can contain two or more exceptions and the exceptional candidates can be placed anywhere in the preference lists, even if the number of types is bounded by a constant. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Stable matchings Stable marriage problem Stable roommate problem NP-hard problems parameterized complexity fixed-parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

A Polynomial-Time Algorithm to Compute Turaev-Viro Invariants TV4,q of 3-Manifolds with Bounded First Betti Number

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2020年第5期20卷 1013-1034页

作者： Maria, Clement Spreer, Jonathan INRIA Sophia Antipolis Mediterranee Valbonne France Univ Sydney Sydney NSW 2006 Australia

In this article, we introduce a fixed-parameter tractable algorithm for computing the Turaev-Viro invariants TV4, q, using the first Betti number, i.e. the dimension of the first homology group of the manifold with Z(2)-coefficients, as parameter. This is, to our knowledge, the first parameterised algorithm in computational 3-manifold topology using a topological parameter. The computation of TV4, q is known to be #P-hard in general;using a topological parameter provides an algorithm polynomial in the size of the input triangulation for the family of 3-manifolds with first Z(2)-homology group of bounded dimension. Our algorithm is easy to implement, and running times are comparable with running times to compute integral homology groups for standard libraries of triangulated 3-manifolds. The invariants we can compute this way are powerful: in combination with integral homology and using standard data sets, we are able to almost double the pairs of 3-manifolds we can distinguish. We hope this qualifies TV4, q to be added to the short list of standard properties (such as orientability, connectedness and Betti numbers) that can be computed ad hoc when first investigating an unknown triangulation.

关键词： fixed-parameter tractable algorithms Turaev-Viro invariants Triangulations of 3-manifolds (Integral)homology (Generalised)normal surfaces Discrete algorithms

来源：评论

学校读者我要写书评

暂无评论

Iterated Type Partitions 31st

Iterated Type Partitions

引用

31st International Workshop on Combinatorial algorithms (IWOCA)

作者： Cordasco, Gennaro Gargano, Luisa Rescigno, Adele A. Univ Campania L Vanvitelli Caserta Italy Univ Salerno Fisciano Italy

ISBN: (纸本)9783030489656;9783030489663

This paper introduces a novel parameter, called iterated type partition, that can be computed in polynomial time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring problem is W[1]-hard when parametrized by the iterated type partition. This result extends to modular-width, answering an open question on the complexity of Equitable Coloring when parametrized by modular-width. On the contrary, we show that the Equitable Coloring problem is FPT when parameterized by neighborhood diversity. Furthermore, we present a scheme for devising FPT algorithms parameterized by iterated type partition, which enables us to find optimal solutions for several graph problems. While the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. As an example, in this paper, we give an algorithm for the Dominating Set problem that outputs an optimal set in time O(2(t) + poly(n)), where n and t are the size and the iterated type partition of the input graph, respectively.

关键词： parameterized complexity fixed-parameter tractable algorithms W[1]-hardness Neighborhood diversity Modular-width

来源：评论

学校读者我要写书评

暂无评论

Backdoors to planning

引用

ARTIFICIAL INTELLIGENCE 2019年 269卷 49-75页

作者： Kronegger, Martin Ordyniak, Sebastian Pfandler, Andreas Johannes Kepler Univ Linz Linz Austria TU Wien Vienna Austria Univ Sheffield Sheffield S Yorkshire England Univ Siegen Siegen Germany

Backdoors measure the distance to tractable fragments and have become an important tool to find fixed-parameter tractable (fpt) algorithms for hard problems in Al and beyond. Despite their success, backdoors have not been used for planning, a central problem in Al that has a high computational complexity. In this work, we introduce two notions of backdoors building upon the causal graph. We analyze the complexity of finding a small backdoor (detection) and using the backdoor to solve the problem (evaluation) in the light of planning with (un)bounded plan length/domain of the variables. For each setting we present either an fpt-result or rule out the existence thereof by showing parameterized intractability. For several interesting cases we achieve the most desirable outcome: detection and evaluation are fpt. In addition, we explore the power of polynomial preprocessing for all fpt-results, i.e., we investigate whether polynomial kernels exist. We show that for the detection problems, polynomial kernels exist whereas we rule out the existence of polynomial kernels for the evaluation problems. (C) 2018 Published by Elsevier B.V

关键词： Planning Backdoors Causal graph fixed-parameter tractable algorithms (parameterized) complexity

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for multi-module capacitated lot-sizing problem, and its generalizations with two-echelons and piecewise concave production costs

A I I E Transactions

引用

A I I E Transactions 2023年第12期55卷

作者： Kartik Kulkarni Manish Bansal Grado Department of Industrial and Systems Engineering Virginia Tech Blacksburg VAUSA

We study new generalizations of the classic capacitated lot-sizing problem with concave production (or transportation), holding, and subcontracting cost functions in which the total production (or transportation) capacity in each time period is the summation of capacities of a subset ofnavailable modules (machines or vehicles) of different capacities. We refer to this problem asMulti-moduleCapacitatedLot-Sizing Problem without or withSubcontracting, and denote it by MCLS or MCLS-S, respectively. These are NP-hard problems ifnis a part of the input and polynomially solvable forn= 1. In this article we address an open question:Does there exist a polynomial time exact algorithm for solving the MCLS or MCLS-S with fixedn≥2?We present exact fixed-parameter tractable (polynomial) algorithms that solve MCLS and MCLS-S inO(T2n+3)time for a givenn≥*** generalizes algorithm of Atamtürk and Hochbaum [Management Science 47(8):1081–1100, 2001] for MCLS-S withn= 1. We also present exact algorithms for two-generalizations of the MCLS and MCLS-S: (a) a lot-sizing problem with piecewise concave production cost functions (denoted by LS-PC-S) that takesO(T2m+3)time, wheremis the number of breakpoints in these functions, and (b) two-echelon MCLS that takesO(T4n+4)time. The former reduces run time of algorithm of Koca et al. [INFORMS J. on Computing 26(4):767–779, 2014] for LS-PC-S by 93.6%, and the latter generalizes algorithm of van Hoesel et al. [Management Science 51(11):1706–1719, 2005] for two-echelon MCLS withn= 1. We perform computational experiments to evaluate the efficiency of our algorithms for MCLS and LS-PC-S and their parallel computing implementation, in comparison to Gurobi 9.1. The results of these experiments show that our algorithms are computationally efficient and stable. Our algorithm for MCLS-S addresses another open question related to the existence of a polynomial time algorithm for optimizing a linear function overn-mixing set (a generalization of the well-kn

关键词： Multi-module capacitated lot-sizing piecewise concave production cost two-echelon capacitated lot-sizing multi-mode lot-sizing n-mixing set fixed-parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

A single-exponential FPT algorithm for the K₄-MINOR COVER problem

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2015年第1期81卷 186-207页

作者： Kim, Eun Jung Paul, Christophe Philip, Geevarghese CNRS LAMSADE Paris France CNRS LIRMM Montpellier France MPII Saarbrucken Germany

Given a graph G and a parameter k is an element of N, the parameterized K-4-MINOR COVER problem asks whether at most k vertices can be deleted to turn G into a K-4-minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied parameterized vertex deletion problems, VERTEX COVER and FEEDBACK VERTEX SET, Which Can also be expressed as TREEWIDTH-t VERTEX DELETION problems: t = 0 for VERTEX COVER and t = 1 for FEEDBACK VERTEX SET. While single-exponential FPT algorithms, i.e. running in 2(O(k)).n(O(1)) co time, are known for these two latter problems, it was open whether the K-4-MINOR COVER problem could be solved in single-exponential EFT time. This paper answers this question in the affirmative. Observe that it is known to be unlikely that TREEWIDTH-t VERTEX DELETION can be solved in time 2(O(k)).n(O(1)). (c) 2014 Published by Elsevier Inc.

关键词： TREEWIDTH-2 DELETION fixed-parameter tractable algorithms K-4-MINOR COVER

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：