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

A simple and fast heuristic for protein structure comparison

BMC BIOINFORMATICS 2008年第1期9卷 1-16页

作者： Pelta, David A. Gonzalez, Juan R. Vega, Marcos Moreno Univ Granada Dept Comp Sci & Artificial Intelligence Models Decis & Optimizat Res Grp E-18071 Granada Spain Univ La Laguna Dept Stat Operat Res & Computat DEIOC E-38207 San Cristobal la Laguna Spain

Background: Protein structure comparison is a key problem in bioinformatics. There exist several methods for doing protein comparison, being the solution of the Maximum Contact Map Overlap problem (MAX-CMO) one of the alternatives available. Although this problem may be solved using exact algorithms, researchers require approximate algorithms that obtain good quality solutions using less computational resources than the formers. Results: We propose a variable neighborhood search metaheuristic for solving MAX-CMO. We analyze this strategy in two aspects: 1) from an optimization point of view the strategy is tested on two different datasets, obtaining an error of 3.5%(over 2702 pairs) and 1.7% (over 161 pairs) with respect to optimal values;thus leading to high accurate solutions in a simpler and less expensive way than exact algorithms;2) in terms of protein structure classification, we conduct experiments on three datasets and show that is feasible to detect structural similarities at SCOP's family and CATH's architecture levels using normalized overlap values. Some limitations and the role of normalization are outlined for doing classification at SCOP's fold level. Conclusion: We designed, implemented and tested. a new tool for solving MAX-CMO, based on a well-known metaheuristic technique. The good balance between solution's quality and computational effort makes it a valuable tool. Moreover, to the best of our knowledge, this is the first time the MAX-CMO measure is tested at SCOP's fold and CATH's architecture levels with encouraging results. Software is available for download at http://***/jrgonzalez/msvns4maxcmo.

关键词： Window Size Area Under Curve exact algorithm Neighborhood Structure Variable Neighborhood Search

来源：评论

学校读者我要写书评

暂无评论

The minimum weight triangulation problem with few inner points

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2006年第3期34卷 149-158页

作者： Hoffmann, Michael Okamoto, Yoshio Toyohashi Univ Technol Dept Informat & Comp Sci Tempa Ku Aichi 4418580 Japan Swiss Fed Inst Technol Inst Theoret Comp Sci CH-8092 Zurich Switzerland

We look at the computational complexity of 2-dimensional geometric optimization problems on a finite point set with respect to the number of inner points (that is, points in the interior of the convex hull). As a case study, we consider the minimum weight triangulation problem. Finding a minimum weight triangulation for a set of n points in the plane is not known to be NP-hard nor solvable in polynomial time, but when the points are in convex position, the problem, can be solved in O(n(3)) time by dynamic programming. We extend the dynamic programming approach to the general problem and describe an exact algorithm which runs in O(6(k) n(5) log n) time where n is the total number of input points and k is the number of inner points. If k is taken as a parameter, this is a fixed-parameter algorithm. It also shows that the problem can be solved in polynomial time if k = O(log n). In fact, the algorithm works not only for convex polygons, but also for simple polygons with k inner points. (C) 2006 Elsevier B.V. All rights reserved.

关键词： exact algorithm fixed-parameter tractability parameterization triangulation

来源：评论

学校读者我要写书评

暂无评论

Definition and algorithms for Reliable Steiner Tree Problem

引用

Journal of Systems Science & Complexity 2015年第4期28卷 876-886页

作者： TANG Yaohua YANG Wenguo GUO Tiande School of Mathematics University of Chinese Academy of Sciences

This paper considers a new form of the Steiner tree problem that is more practical and reliable,which we call Reliable Steiner Tree(RST)*** authors give a detailed definition for this new problem and design both an exact algorithm and an approximation algorithm for *** definition is based on the reliability of full components instead of Steiner *** task is thus to find the most reliable full components to make up an optimum reliable Steiner *** exact algorithm designed for this problem utilizes a dynamic programming *** approximation algorithm designed in this paper exploits a local search strategy that looks for the best full component according to a selection function at a time.

关键词： Approximation algorithm exact algorithm reliability steiner tree.

来源：评论

学校读者我要写书评

暂无评论

Channel assignment via fast zeta transform

引用

INFORMATION PROCESSING LETTERS 2011年第15期111卷 727-730页

作者： Cygan, Marek Kowalik, Lukasz Univ Warsaw Inst Informat PL-00325 Warsaw Poland

We show an 0*((l + 1)(n))-time algorithm for the channel assignment problem, where l is the maximum edge weight. This improves on the previous o*((l + 2)(n))-time algorithm by Kral (2005) [1], as well as algorithms for important special cases, like L(2, 1)-labeling. For the latter problem, our algorithm works in 0*(3(n)) time. The progress is achieved by applying the fast zeta transform in combination with the inclusion-exclusion principle. (C) 2011 Elsevier B.V. All rights reserved.

关键词： algorithms Channel assignment Inclusion-exclusion exact algorithm L(2,1)-labeling

来源：评论

学校读者我要写书评

暂无评论

Optimization Coordinated seru scheduling and distribution operation problems with DeJong's learning effects

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第2期313卷 452-464页

作者： Zhang, Zhe Song, Xiaoling Gong, Xue Yin, Yong Lev, Benjamin Zhou, Xiaoyang Nanjing Univ Sci & Technol Sch Econ & Management Nanjing 210094 Peoples R China Doshisha Univ Grad Sch Business Karasuma Imadegawa Kamigyo-ku Kyoto 6028580 Japan Drexel Univ LeBow Coll Business Dept Decis Sci Philadelphia PA 19104 USA Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China

Inspired by the advantage of just-in-time philosophy, zero-inventory is common in many industries, es-pecially those need fast response with a short lifespan. Accordingly, this paper focuses on coordinated production scheduling and distribution operation problems considering workers' DeJong's learning effects in seru production system (SPS), in which seru is a relatively new-type manufacturing mode originating from Japan and can achieve fast response in practice. Two variants of coordinated seru scheduling and distribution operation problems are studied, and the corresponding 0-1 integer programming model is formulated. By analyzing the mathematical property, the polynomial computation time of the former is able to be determined, and an intractability and NP-hardness proof is provided for the latter. The dynamic programming-based exact algorithm and the heuristic ant colony optimization algorithm are developed respectively. Computational experiments are conducted finally, and a series of experimental results indicate that the Dejong's learning effect has a significant influence on coordinated seru scheduling and distribution operation problems, meanwhile a remarkable benefit (the average improvement is 16.97%) can be achieved by the coordinated production scheduling and distribution operation in SPS.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Scheduling Seru production Distribution operation exact algorithm Heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

Complexity of Grundy coloring and its variants

引用

DISCRETE APPLIED MATHEMATICS 2018年 243卷 99-114页

作者： Bonnet, Edouard Foucaud, Florent Kim, Eun Jung Sikora, Florian Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary Univ Blaise Pascal CNRS LIMOS Clermont Ferrand France PSL Res Univ Univ Paris Dauphine CNRS LAMSADE Paris France ENS Lyon LIP Lyon France

The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of GRUNDY COLORING, the problem of determining whether a given graph has Grundy number at least k. We also study the variants WEAK GRUNDY COLORING (where the coloring is not necessarily proper) and CONNECTED GRUNDY COLORING (where at each step of the greedy coloring algorithm, the subgraph induced by the colored vertices must be connected). We show that GRUNDY COLORING can be solved in time O*(2.443(n)) and WEAK GRUNDY COLORING in time O*(2.716(n)) on graphs of order n. While GRUNDY COLORING and WEAK GRUNDY COLORING are known to be solvable in time O*(2(0(wk))) for graphs of treewidth w (where k is the number of colors), we prove that under the Exponential Time Hypothesis (ETH), they cannot be solved in time O*(2(0(w log w)))). We also describe an O*(2(20(k))) algorithm for WEAK GRUNDY COLORING, which is therefore FPT for the parameter k. Moreover, under the ETH, we prove that such a running time is essentially optimal (this lower bound also holds for GRUNDY COLORING). Although we do not know whether GRUNDY COLORING is in FPT, we show that this is the case for graphs belonging to a number of standard graph classes including chordal graphs, claw-free graphs, and graphs excluding a fixed minor. We also describe a quasi-polynomial time algorithm for GRUNDY COLORING and WEAK GRUNDY COLORING on apex-minor graphs. In stark contrast with the two other problems, we show that CONNECTED GRUNDY COLORING is NP-complete already for k = 7 colors. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Grundy coloring Computational complexity Weak Grundy Connected Grundy exact algorithm Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Modeling and solving the waste valorization production and distribution scheduling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第1期306卷 400-417页

作者： Chagas, Guilherme O. Coelho, Leandro C. Darvish, Maryam Renaud, Jacques Univ Laval CIRRELT Quebec City PQ Canada Univ Laval Fac Sci Adm Quebec City PQ Canada Univ Laval Canada Res Chair Integrated Logist Quebec City PQ Canada

Bio-based waste valorization is one of the current trends in municipal waste management. It decreases the amount of waste to be disposed of, reduces the sourcing of limited chemical compounds used in fertilizer production, and promotes a circular economy perspective vital in big cities. However, model-ing and optimizing a biorefinery plant's operations is challenging and requires innovative approaches and solutions. In this paper, we model and solve the integrated production and distribution scheduling problem faced by an industrial partner. We propose three models for the waste valorization production and distribution scheduling problem: a time-discretized integer linear program, and two mixed-integer linear program with continuous timing variables. Moreover, several powerful and problem-specific valid inequalities and variable reduction procedures are proposed. We study some variants of the problem and propose a simple heuristic algorithm that mimics the logic of a decision maker. Through a series of com-putational experiments, we determine how critical operational parameters affect the performance of the system and demonstrate how significant improvements can be achieved in our industrial partner's biore-finery plant.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Distribution Production scheduling Waste valorization exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for spare allocation problems

引用

IEEE TRANSACTIONS ON RELIABILITY 2006年第2期55卷 369-378页

作者： Lin, Hung-Yau Yeh, Fu-Min Kuo, Sy-Yen Natl Taiwan Univ Dept Elect Engn Taipei 106 Taiwan Chung Shan Inst Sci & Technol Taoyuan Taiwan Natl Taiwan Ocean Univ Dept Comp Sci & Engn Chilung Taiwan

The spare allocation problem in redundant RAM is to replace faulty rows/columns of memory cells with spare rows/columns. To solve the problem, comparison-based search tree structures were used in traditional exact algorithms. These algorithms are not efficient for large problems because significant amounts of data have to be retained and copied in order to generate new partial solutions. Many data may need to be compared for the removal of each redundant partial solution. To overcome these drawbacks, an efficient algorithm is proposed in this paper. The algorithm transforms a spare allocation problem into Boolean functions, and the renowned BDD is used to manipulate them. Experimental results indicate that the proposed algorithm is very efficient in terms of speed and memory requirements. It may also be useful for problems which can be modeled as constraint bipartite vertex cover problems.

关键词： BDD bipartite graph Boolean functions exact algorithm memory repair RRAM vertex cover

来源：评论

学校读者我要写书评

暂无评论

On exact solutions to the Euclidean bottleneck Steiner tree problem

引用

INFORMATION PROCESSING LETTERS 2010年第16期110卷 672-678页

作者： Bae, Sang Won Lee, Chunseok Choi, Sunghee Kyonggi Univ Dept Comp Sci Suwon South Korea Korea Adv Inst Sci & Technol Dept Comp Sci Taejon 305701 South Korea

We study the Euclidean bottleneck Steiner tree problem: given a set P of n points in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edge in the tree is minimized. This problem is known to be NP-hard even to approximate within ratio root 2 and there was no known exact algorithm even for k = 1 prior to this work. In this paper, we focus on finding exact solutions to the problem for a small constant k. Based on geometric properties of optimal location of Steiner points, we present an optimal Theta(n log n)-time exact algorithm for k = 1 and an O(n(2))-time algorithm for k = 2. Also, we present an optimal Theta(n log n)-time exact algorithm for any constant k for a special case where there is no edge between Steiner points. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Computational geometry Bottleneck Steiner tree exact algorithm Farthest-color Voronoi diagram

来源：评论

学校读者我要写书评

暂无评论

Mitigating overtime risk in tactical surgical scheduling

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2020年 93卷

作者： Zhang, Yu Wang, Yu Tang, Jiafu Lim, Andrew Southwestern Univ Finance & Econ Sch Business Adm Chengdu 611130 Peoples R China Northeastern Univ Sch Business Adm Dept Management Sci & Engn Shenyang 110004 Peoples R China Dongbei Univ Finance & Econ Coll Management Sci & Engn Dalian 116025 Peoples R China Natl Univ Singapore Dept Ind Syst Engn & Management Singapore 117576 Singapore

Overtime is a common phenomenon in surgery departments, causing stress to physicians, dissatisfaction to patients, and financial loss to hospitals. We help risk-averse managers of operating rooms (ORs) to mitigate overtime in tactical surgery scheduling, which determines the assignment of elective patients to available ORs in upcoming time periods. We model the uncertain surgical durations via partial, full, or empirical distributions. To mitigate overtime, our model maximizes the risk aversion level of the OR manager (and thus the risk-hedging ability of the solution) while ensuring that the certainty equivalent of surgery duration in each OR at each time period does not exceed the stipulated working hours. The corresponding decision criterion, termed the maximized risk aversion level, is demonstrated in theory and in numerical experiments to be able to mitigate both the overtime probability and the expected overtime duration. To solve the problem, we develop an exact hill-climbing algorithm and demonstrate its convergence and correctness. Numerical experiments based on real-life surgery data show that our method outperforms the existing methods in several indicators that of concern to OR managers. In particular, this method is computationally amiable and hence is applicable to larger-scale instances. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Surgery scheduling Overtime Risk aversion exact algorithm Healthcare

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：