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

combinatorial RNA Design: Designability and Structure-Approximating Algorithm in Watson-Crick and Nussinov-Jacobson Energy Models

引用

ALGORITHMICA 2017年第3期79卷 835-856页

作者： Hales, Jozef Heliou, Alice Manuch, Jan Ponty, Yann Stacho, Ladislav Ecole Polytech LIX CNRS UMR 7161 Palaiseau France Inria Saclay Palaiseau France Simon Fraser Univ Dept Math Burnaby BC Canada Univ British Columbia Dept Comp Sci Vancouver BC Canada

We consider the combinatorial RNA Design problem, a minimal instance of RNA design where one must produce an RNA sequence that adopts a given secondary structure as its minimal free-energy structure. We consider two free-energy models where the contributions of base pairs are additive and independent: the purely combinatorial Watson-Crick model, which only allows equally-contributing A-U and C-G base pairs, and the real-valued Nussinov-Jacobson model, which associates arbitrary energies to A-U, C-G and G-U base pairs. We first provide a complete characterization of designable structures using restricted alphabets and, in the four-letter alphabet, provide a complete characterization for designable structures without unpaired bases. When unpaired bases are allowed, we characterize extensive classes of (non-) designable structures, and prove the closure of the set of designable structures under the stutter operation. Membership of a given structure to any of the classes can be tested in Theta(n) time, including the generation of a solution sequence for positive instances. Finally, we consider a structure-approximating relaxation of the design, and provide a Theta(n) algorithm which, given a structure S that avoids two trivially non-designable motifs, transforms S into a designable structure constructively by adding at most one base-pair to each of its stems.

关键词： RNA structure inverse combinatorial optimization String design

来源：评论

学校读者我要写书评

暂无评论

A simple algorithm and min-max formula for the inverse arborescence problem

引用

DISCRETE APPLIED MATHEMATICS 2021年 295卷 85-93页

作者： Frank, Andras Hajdu, Gergely Eotvos Lorand Univ Dept Operat Res MTA ELTE Egervary Res Grp Pazmany P S 1-C H-1117 Budapest Hungary

In 1998, Hu and Liu developed a strongly polynomial algorithm for solving the inverse arborescence problem that aims at minimally modifying a given cost-function on the edge-set of a digraph D so that an input spanning arborescence of D becomes a cheapest one. In this note, we develop a conceptually simpler algorithm along with a new min-max formula for the minimum modification of the cost-function. The approach is based on a link to a min-max theorem and a simple (two-phase greedy) algorithm by the first author from 1979 concerning the primal optimization problem of finding a cheapest subgraph of a digraph that covers an intersecting family along with the corresponding dual optimization problem, as well. (C) 2021 The Author(s). Published by Elsevier B.V.

关键词： inverse combinatorial optimization Arborescence Min-max theorem Simple algorithm

来源：评论

学校读者我要写书评

暂无评论

The inverse maximum flow problem considering l_∞ norm

引用

RAIRO-OPERATIONS RESEARCH 2008年第3期42卷 401-414页

作者： Deaconu, Adrian Univ Transilvania Brasov Fac Math & Informat Theoret Comp Sci Dept Brasov Romania

The problem is to modify the capacities of the arcs from a network so that a given feasible flow becomes a maximum flow and the maximum change of the capacities on arcs is minimum. A very fast O(m . log(n)) time complexity algorithm for solving this problem is presented, where m is the number of arcs and n is the number of nodes of the network. The case when both, lower and upper bounds of the flow can be modified so that the given feasible flow becomes a maximum flow is also discussed. The algorithm proposed can be adapted to solve this problem, too. The inverse minimum flow problem considering l(infinity) norm is also studied.

关键词： inverse combinatorial optimization maximum flow strongly polynomial time complexity

来源：评论

学校读者我要写书评

暂无评论

The 0-1 inverse maximum stable set problem

引用

DISCRETE APPLIED MATHEMATICS 2008年第13期156卷 2501-2516页

作者： Chung, Yerim Demange, Marc ESSEC Business Sch Cergy France Univ Paris 01 Paris Sch Econ F-75231 Paris 05 France

In this paper we study the 0-1 inverse maximum stable set problem, denoted by IS([0,1]). Given a graph and a fixed stable set, it is to delete the minimum number of vertices to make this stable set maximum ill the new graph. We also consider IS([0,1]) against a Specific algorithm such as Greedy and 2opt, aiming to delete the minimum number of vertices so that the algorithm selects the given stable set in the new graph;we denote them by IS([0,1],greedy) and IS([0,1],2opt), respectively. Firstly, we show that they are NIP-hard. even if the fixed stable set contains only one vertex. Secondly, we achieve an approximation ratio of 2 - circle minus(1/root log Delta) for IS([0,1],2opt). Thirdly, we study the tractability of IS([0,1]) for some classes of perfect graphs such as comparability, co-comparability and chordal graphs. Finally, we compare the hardness of IS([0,1]) and IS([0,1],2opt) for some other classes of graphs. (c) 2008 Published by Elsevier B.V.

关键词： inverse combinatorial optimization maximum stable set problem NP-hardness approximation ratio perfect graphs

来源：评论

学校读者我要写书评

暂无评论

inverse chromatic number problems in interval and permutation graphs

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第3期243卷 763-773页

作者： Chung, Yerim Culus, Jean-Francois Demange, Marc Yonsei Univ Sch Business Seoul 120749 South Korea Univ Antilles Guyane CEREGMIA Schoelcher Martinique France RMIT Univ Sch Math & Geospatial Sci Melbourne Vic Australia CNRS UMR 7243 LAMSADE Paris France

Given a graph G and a positive integer K, the inverse chromatic number problem consists in modifying the graph as little as possible so that it admits a chromatic number not greater than K. In this paper, we focus on the inverse chromatic number problem for certain classes of graphs. First, we discuss diverse possible versions and then focus on two application frameworks which motivate this problem in interval and permutation graphs: the inverse booking problem and the inverse track assignment problem. The inverse booking problem is closely related to some previously known scheduling problems;we propose new hardness results and polynomial cases. The inverse track assignment problem motivates our study of the inverse chromatic number problem in permutation graphs;we show how to solve in polynomial time a generalization of the problem with a bounded number of colors. (C) 2014 Elsevier By. All rights reserved.

关键词： inverse combinatorial optimization Graph coloring Interval graphs Permutation graphs

来源：评论

学校读者我要写书评

暂无评论

inverse feasibility problems of the inverse maximum flow problems

引用

SADHANA-ACADEMY PROCEEDINGS IN ENGINEERING SCIENCES 2013年第2期38卷 199-209页

作者： Deaconu, Adrian Ciurea, Eleonor Transilvania Univ Brasov Fac Math & Informat Dept Math & Comp Sci Brasov Romania

A linear time method to decide if any inverse maximum flow (denoted General inverse Maximum Flow problems (IMFG)) problem has solution is deduced. If IMFG does not have solution, methods to transform IMFG into a feasible problem are presented. The methods consist of modifying as little as possible the restrictions to the variation of the bounds of the flow. New inverse combinatorial optimization problems are introduced and solved.

关键词： inverse combinatorial optimization maximum flow minimum cut

来源：评论

学校读者我要写书评

暂无评论

An inverse economic lot-sizing approach to eliciting supplier cost parameters

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 2014年第0期149卷 80-88页

作者： Egri, Peter Kis, Tamas Kovacs, Andras Vancza, Jozsef Hungarian Acad Sci Fraunhofer Project Ctr Prod Management & Informat Inst Comp Sci & Control H-1051 Budapest Hungary Budapest Univ Technol & Econ Dept Mfg Sci & Technol Budapest Hungary

Recent literature on supply chain coordination offers a wide range of game theoretic and optimization approaches that ensure efficient planning in the supply chain, but assume that the involved parties have complete information about each other. However, in reality, complete information is rarely available, and those models alone do not present any incentive for the parties to reveal their private information, e.g., the cost parameters that they use when solving their planning problems. This paper proposes an inverse lot-sizing model for eliciting the cost parameters of a supplier from historic demand vs. optimal delivery lot-size pairs, gathered during repeated earlier encounters. It is assumed that the supplier solves a single-item, multi-period, uncapacitated lot-sizing problem with backlogs to optimality to calculate its lot-sizes, and the buyer is aware of this fact. The inverse lot-sizing problem is reformulated to an inverse shortest path problem, which is, in turn, solved as a linear program. This model is used to compute the ratios of the supplier's cost parameters, i.e., the setup, the holding, and the backlog cost parameters consistent with all the historic samples. The elicited cost parameters can be used as input for various game theoretic or bilevel optimization models for supply chain coordination. Computational experiments on randomly generated problem instances indicate that the approach is very efficient in predicting future supplier actions from the historic records. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Economic lot-sizing inverse combinatorial optimization Eliciting cost parameters

来源：评论

学校读者我要写书评

暂无评论

The 0-1 inverse maximum independent set problem on forests and unicyclic graphs

引用

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS 2016年第2期8卷 1650019-1-1650019-8页

作者： Liu, Shuaifu Zhang, Zhao Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Xinjiang Peoples R China Zhejiang Normal Univ Coll Math Phys & Informat Engn Jinhua 321004 Zhejiang Peoples R China

Given a graph G and an independent set S of G, the 0-1 inverse maximum independent set problem (IMIS0,1) is to delete as few vertices as possible such that S becomes a maximum independent set of G. It is known that IMIS0,1 is NP-hard even when the given independent set has a bounded size. In this paper, we present linear-time algorithms for IMIS0,1 on forests and unicyclic graphs.

关键词： inverse combinatorial optimization independent set algorithm

来源：评论

学校读者我要写书评

暂无评论

An inverse economic lot-sizing approach to eliciting supplier cost parameters

An inverse economic lot-sizing approach to eliciting supplie...

引用

17th International Working Seminar on Production Economics

关键词： Economic lot-sizing inverse combinatorial optimization Eliciting cost parameters

来源：评论

学校读者我要写书评

暂无评论

Some inverse Traveling Salesman Problems

引用

Electronic Notes in Discrete Mathematics 2008年第C期30卷 9-14页

作者： Chung, Yerim Demange, Marc Paris School of Economics Paris 1 University France Département SID ESSEC Cergy Pontoise France

Usual inverse combinatorial optimization problems consist in modifying as little as possible the instance parameters to make a given solution optimal. In this paper we consider several extensions taking into account constraints on the weight system and inverse problems against a specific algorithm. We consider TSP under this point of view and devise both complexity and approximation results. © 2008 Elsevier B.V. All rights reserved.

关键词： 2opt inverse combinatorial optimization TSP TSP{1,2}

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：