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

2-Interconnected facility location: Specification, complexity, and exact solutions

Electronic Notes in Discrete Mathematics 2013年 41卷 21-28页

作者： Chimani, Markus Kandyba, Maria Martens, Maren Faculty of Mathematics and Computer Science Uni Jena Germany

Connected facility location combines cost-efficient facility placement and the requirement to connect the facilities among each other. Such problems arise, e.g., in telecommunication applications where networks consist of a central core and local clients connected to it. Reliability of the core is a central issue, and we may hence require the core to be at least *** establish the problem class of 2-interConnected Facility Location (2-iCFL), categorize its central variants, and prove that they are hard to approximate. However, our computational results show that our orientation-based ILPs allow us to effectively solve such problems to optimality for hundreds of nodes. We also establish constructive characterizations for feasible problem instances, to be used for algorithmic feasibility checks, preprocessing, and heuristics. © 2013 Elsevier B.V.

关键词： 2-connectivity exact algorithms Experiments Facility location Inapproximability Integer programming

来源：评论

学校读者我要写书评

暂无评论

An Efficient Algorithm to Identify DNA Motifs

引用

MATHEMATICS IN COMPUTER SCIENCE 2013年第4期7卷 387-399页

作者： Abbass, Mostafa M. Bahig, Hazem M. Sinai Univ Fac Engn Dept Basic Sci Sinai Egypt Qatar Univ Coll Engn KINDI Lab Comp Res Doha Qatar Hail Univ Coll Comp Sci & Engn Comp Sci & Software Engn Dept Hail Saudi Arabia Ain Shams Univ Fac Sci Dept Math Div Comp Sci Cairo Egypt

We consider the problem of identifying motifs that abstracts the task of finding short conserved sites in genomic DNA. The planted (l, d)- motif problem, PMP, is the mathematical abstraction of this problem, which consists of finding a substring of length l that occurs in each si in a set of input sequences S = {s1, s2,..., st} with at most d substitutions. Our propose algorithm combines the voting algorithm and pattern matching algorithm to find exact motifs. The combined algorithm is achieved by running the voting algorithm on t' sequences, t' < t. After that we use the pattern matching on the output of the voting algorithm and the reminder sequences, t - t'. Two values of t' are calculated. The first value of t' makes the running time of our proposed algorithm less than the running time of voting algorithm. The second value of t' makes the running time of our proposed algorithm is minimal. We show that our proposed algorithm is faster than the voting algorithm by testing both algorithms on simulated data from (9, d <= 2) to (19, (d <= 7). Finally, we test the performance of the combined algorithm on realistic biological data.

关键词： DNA motifs Transcription factor binding sites exact algorithms Pattern matching Planted (l,d)-motif

来源：评论

学校读者我要写书评

暂无评论

StemFinder: An Efficient Algorithm for Searching Motif Stems over Large Alphabets

StemFinder: An Efficient Algorithm for Searching Motif Stems...

引用

IEEE International Conference on Bioinformatics and Biomedicine (IEEE BIBM)

作者： Yu, Qiang Huo, Hongwei Vitter, Jeffrey Scott Huan, Jun Nekrich, Yakov Xidian Univ Sch Comp Sci & Technol Xian 710071 Peoples R China Univ Kansas Natl Telecommun Technol Ctr Lawrence KS 66047 USA

ISBN: (纸本)9781479913091;9781479913107

Motif stem search (MSS) is a recent motif search problem to search motifs on large-alphabet inputs. A motif stem is an l-length string with some wildcards. The goal of the MSS problem is to find a set of stems that represents a superset of all (l, d) motifs present in the input sequences. The three main contributions of this paper are as follows: (1) We build motif stem representation more precisely by using regular expressions. (2) We give a new method for generating all possible motif stems. (3) We propose an efficient algorithm, called StemFinder, for solving the MSS problem. Compared with the previous algorithms, StemFinder runs much faster and first solves the (17, 8), (19, 9) and (21, 10) challenging instances on protein sequences;moreover, StemFinder reports fewer stems representing a smaller superset of all (l, d) motifs.

关键词： Planted motif search motif stem search exact algorithms regular expressions

来源：评论

学校读者我要写书评

暂无评论

Uniqueness, intractability and exact algorithms: Reflections on level-κ phylogenetic networks

引用

Journal of Bioinformatics and Computational Biology 2009年第4期7卷 597-623页

作者： Van Iersel, Leo Kelk, Steven Mnich, Matthias Department of Mathematics and Computer Science Technische Universiteit Eindhoven 5600 MB Eindhoven P. O. Box 513 Netherlands Centrum voor Wiskunde en Informatica (CWI) 1090 GB Amsterdam P. O. Box 94079 Netherlands

Phylogenetic networks provide a way to describe and visualize evolutionary histories that have undergone so-called reticulate evolutionary events such as recombination, hybridization or horizontal gene transfer. The level κ of a network determines how non-treelike the evolution can be, with level-0 networks being trees. We study the problem of constructing level-κ phylogenetic networks from triplets, i.e. phylogenetic trees for three leaves (taxa). We give, for each κ, a level-κ network that is uniquely defined by its triplets. We demonstrate the applicability of this result by using it to prove that (1) for all κ ≥ 1 it is NP-hard to construct a level-κ network consistent with all input triplets, and (2) for all κ ≥ 0 it is NP-hard to construct a level-κ network consistent with a maximum number of input triplets, even when the input is dense. As a response to this intractability, we give an exact algorithm for constructing level-1 networks consistent with a maximum number of input triplets. © 2009 Imperial College Press.

关键词： exact algorithms NP-hardness Phylogenetic networks

来源：评论

学校读者我要写书评

暂无评论

An Experimental Study of Minimum Routing Cost Spanning Tree algorithms

An Experimental Study of Minimum Routing Cost Spanning Tree ...

引用

International Conference of Soft Computing and Pattern Recognition (SoCPaR)

作者： Quoc Phan Tan Nghia Nguyen Duc Saigon Univ Dept Informat Technol Ho Chi Minh City Vietnam Ha Noi Univ Sci & Technol Sch Informat & Commun Technol Hanoi Vietnam

ISBN: (纸本)9781479934003

The task of finding the Minimum Routing Cost Spanning Tree (MRCST) can be found in many network design problems. In general cases, MRCST problem is a NP-hard problem. Till now, several algorithms for solving the problem are proposed and their performance were evaluated on different data sets. This paper presents a short survey of well known MRCST algorithms and gives a report on an extensive experimentation based on benchmark instances collected from the literature. In addition, the paper is also the first pioneering research that experiment on graphs with up to 1000 vertices.

关键词： minimum routing cost spanning tree heuristic metaheuristic swarm intelligence approximation scheme exact algorithms

来源：评论

学校读者我要写书评

暂无评论

The Implicit Hitting Set Approach to Solve Combinatorial Optimization Problems with an Application to Multigenome Alignment

引用

OPERATIONS RESEARCH 2013年第2期61卷 453-468页

作者： Moreno-Centeno, Erick Karp, Richard M. Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Int Comp Sci Inst Berkeley CA 94704 USA

We develop a novel framework, the implicit hitting set approach, for solving a class of combinatorial optimization problems. The explicit hitting set problem is as follows: given a set U and a family S of subsets of U, find a minimum-cardinality set that intersects (hits) every set in S. In the implicit hitting set problem (IHSP), the family of subsets S is not explicitly listed (its size is, generally, exponential in terms of the size of U);instead, it is given via a polynomial-time oracle that verifies if a given set H is a hitting set or returns a set in S that is not hit by H. Many NP-hard problems can be straightforwardly formulated as implicit hitting set problems. We show that the implicit hitting set approach is valuable in developing exact and heuristic algorithms for solving this class of combinatorial optimization problems. Specifically, we provide a generic algorithmic strategy, which combines efficient heuristics and exact methods, to solve any IHSP. Given an instance of an IHSP, the proposed algorithmic strategy gives a sequence of feasible solutions and lower bounds on the optimal solution value and ultimately yields an optimal solution. We specialize this algorithmic strategy to solve the multigenome alignment problem and present computational results that illustrate the effectiveness of the implicit hitting set approach.

关键词： combinatorial optimization exact algorithms heuristic algorithms multigenome alignment problem multisequence alignment problem

来源：评论

学校读者我要写书评

暂无评论

A mixed integer linear programming model to reconstruct phylogenies from single nucleotide polymorphism haplotypes under the maximum parsimony criterion

引用

algorithms FOR MOLECULAR BIOLOGY 2013年第1期8卷 3-3页

作者： Catanzaro, Daniele Ravi, Ramamoorthi Schwartz, Russell Univ Libre Bruxelles Dept Comp Sci B-1050 Brussels Belgium Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA Carnegie Mellon Univ Dept Biol Sci Pittsburgh PA 15213 USA Carnegie Mellon Univ Lane Ctr Computat Biol Pittsburgh PA 15213 USA

Background: Phylogeny estimation from aligned haplotype sequences has attracted more and more attention in the recent years due to its importance in analysis of many fine-scale genetic data. Its application fields range from medical research, to drug discovery, to epidemiology, to population dynamics. The literature on molecular phylogenetics proposes a number of criteria for selecting a phylogeny from among plausible alternatives. Usually, such criteria can be expressed by means of objective functions, and the phylogenies that optimize them are referred to as optimal. One of the most important estimation criteria is the parsimony which states that the optimal phylogeny T* for a set H of n haplotype sequences over a common set of variable loci is the one that satisfies the following requirements: (i) it has the shortest length and (ii) it is such that, for each pair of distinct haplotypes hi, hj is an element of H, the sum of the edge weights belonging to the path from hi to hj in T* is not smaller than the observed number of changes between hi and hj. Finding the most parsimonious phylogeny for H involves solving an optimization problem, called the Most Parsimonious Phylogeny Estimation Problem (MPPEP), which isNP-hard in many of its versions. Results: In this article we investigate a recent version of the MPPEP that arises when input data consist of single nucleotide polymorphism haplotypes extracted from a population of individuals on a common genomic region. Specifically, we explore the prospects for improving on the implicit enumeration strategy of implicit enumeration strategy used in previous work using a novel problem formulation and a series of strengthening valid inequalities and preliminary symmetry breaking constraints to more precisely bound the solution space and accelerate implicit enumeration of possible optimal phylogenies. We present the basic formulation and then introduce a series of provable valid constraints to reduce the solution space. We the

关键词： Combinatorial optimization exact algorithms Mixed integer programming Phylogeny estimation Haplotype estimation Maximum parsimony Single nucleotide polymorphism Computational biology

来源：评论

学校读者我要写书评

暂无评论

The max quasi-independent set problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2012年第1期23卷 94-117页

作者： Bourgeois, N. Giannakos, A. Lucarelli, G. Milis, I. Paschos, V. T. Pottie, O. CNRS LAMSADE FRE 3234 Paris France Univ Paris 09 Paris France Athens Univ Econ & Business Dept Informat Athens Greece

In this paper, we deal with the problem of finding quasi-independent sets in graphs. This problem is formally defined in three versions, which are shown to be polynomially equivalent. The one that looks most general, namely, f -MAX QUASIINDEPENDENT SET, consists of, given a graph and a non-decreasing function f, finding a maximum size subset Q of the vertices of the graph, such that the number of edges in the induced subgraph is less than or equal to f (|Q|). For this problem, we show an exact solution method that runs within time O*(2(d-27/23/d+1 n)) on graphs of average degree bounded by d. For the most specifically defined gamma-MAX QUASI-INDEPENDENT SET and k-MAX QUASI-INDEPENDENT SET problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested.

关键词： Quasi independent set exact algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Rescheduling for new orders on a single machine with setup times

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2012年第1期223卷 40-46页

作者： Hoogeveen, H. Lente, C. T'kindt, V. Univ Tours Lab Inforrnat EA 6300 ERL CNRS 6305 Equipe Ordonnancement & Conduite F-37200 Tours France Univ Utrecht NL-3508 TB Utrecht Netherlands

We focus on some single machine scheduling problems for which a set of new jobs have to be scheduled after a schedule of old jobs has been set. Each new and old job belongs to a family and changing the production from one family to another requires a setup. The initial schedule of old jobs is assumed to minimize the sum of setup times. The new jobs can be either scheduled after the old jobs or inserted within the existing schedule, which results in a disruption cost that has to be minimized together with the sum of setup times of the overall schedule. In this paper we tackle several simple setup time configurations yielding different scheduling problems for which we propose optimal polynomial time algorithms or provide NP-hardness proofs. In the former case we consider the problem of enumerating the set of strict Pareto optima for the sum of setup times and disruption cost criteria. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Scheduling New orders Multicriteria exact algorithms Complexity proofs

来源：评论

学校读者我要写书评

暂无评论

Bandwidth and distortion revisited

引用

DISCRETE APPLIED MATHEMATICS 2012年第4-5期160卷 494-504页

作者： Cygan, Marek Pilipczuk, Marcin Univ Warsaw Fac Math Comp Sci & Mech PL-02092 Warsaw Poland

In this paper we merge recent developments on exact algorithms for finding an ordering of vertices of a given graph that minimizes bandwidth (the BANDWIDTH problem) and for finding an embedding of a given graph into a line that minimizes distortion (the DISTORTION problem). For both problems we develop algorithms that work in O(9.363(n)) time and polynomial space. For BANDWIDTH, this improves O*(10(n)) algorithm by Feige and Kilian from 2000, for DISTORTION this is the first polynomial space exact algorithm that works in O(c(n)) time we are aware of. As a byproduct, we enhance the O(5(n+o(n)))-time and O*(2(n))-space algorithm for DISTORTION by Fomin et al. to an algorithm working in O(4.383(n))-time and space. (c) 2011 Elsevier B.V. All rights reserved.

关键词： Bandwidth Distortion exact algorithms Exponential algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：