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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Isolation concepts for clique enumeration: Comparison and computational experiments

引用

THEORETICAL COMPUTER SCIENCE 2009年第52期410卷 5384-5397页

作者： Hueffner, Falk Komusiewicz, Christian Moser, Hannes Niedermeier, Rolf Univ Jena Inst Informat D-07743 Jena Germany Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

We do Computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. We compare three isolation concepts and their combination with two enumeration modi for maximal cliques ("isolated maximal" vs "maximal isolated"). All studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter "degree of isolation". We provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the G(n,m,p) model), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks. (C) 2009 Elsevier B.V. All rights reserved.

关键词： NP-hard problem Fixed-parameter tractability exact algorithm algorithm engineering Dense subgraph

来源：评论

学校读者我要写书评

暂无评论

Reducing the total tardiness by Seru production: model, exact and cooperative coevolution solutions

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2020年第21期58卷 6441-6452页

作者： Sun, Wei Yu, Yang Lou, Qi Wang, Junwei Guan, Yuechao Liaoning Univ Business Sch Shenyang Liaoning Peoples R China Northeastern Univ Inst Intelligent Syst Shenyang Liaoning Peoples R China Univ Hong Kong Dept Ind & Mfg Syst Engn Hong Kong Peoples R China

Seru Production is widely used in the Japanese electronics industry owing to its benefits. The total tardiness can be significantly reduced by Seru Production. We focus on investigating the fundamental principle of the total tardiness reduction brought by Seru Production. We formulate the seru system operation with minimising the total tardiness and analyse the solution space. We clarify that the model is non-linear. To exactly obtain the optimal solution of the non-linear model, we decompose the non-linear model into seru formation and seru scheduling which is formulated as a linear model. Thus, the small-scale seru system operation with minimising the total tardiness is solved exactly. For the large-scale problems, we propose a cooperative coevolution algorithm, where two evolution algorithms deal with the seru formation and seru scheduling. In the coevolution process, the two algorithms perform cooperation to seek the better solutions of seru system operation with minimising the total tardiness. Extensive experiments are tested to investigate how Seru Production reduces the total tardiness.

关键词： cooperative coevolution due date exact algorithm manufacturing tardiness

来源：评论

学校读者我要写书评

暂无评论

Determining the L(2,1)-span in polynomial space

引用

DISCRETE APPLIED MATHEMATICS 2013年第13-14期161卷 2052-2061页

作者： Junosza-Szaniawski, Konstanty Kratochvil, Jan Liedloff, Mathieu Rzazewski, Pawei Warsaw Univ Technol Fac Math & Informat Sci PL-00662 Warsaw Poland Charles Univ Prague Dept Appl Math CR-11800 Prague 1 Czech Republic Univ Orleans Lab Informat Fondamentale Orleans F-45067 Orleans 2 France

A k-L(2, 1)-labeling of a graph is a mapping from its vertex set into a set of integers {0, ... , k} such that adjacent vertices get labels that differ by at least 2 and vertices in distance 2 get different labels. The main result of the paper is an algorithm finding an optimal L(2, 1)-labeling of a graph (i.e. an L(2, 1)-labeling in which the largest label is the least possible) in time 0*(7.4922(n)) and polynomial space. Then we adapt our method to obtain a faster algorithm for k-L(2, 1)-labeling, where k is a small positive constant. Moreover, a new interesting extremal graph theoretic problem is defined and solved. (C) 2013 Elsevier B.V. All rights reserved.

关键词： L(2,1)-labeling Channel assignment problem exact algorithm Polynomial space Red-black graph

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for the collapsing knapsack problem

引用

INFORMATION SCIENCES 2006年第12期176卷 1739-1751页

作者： Wu Jigang Srikanthan, Thambipillai Nanyang Technol Univ Sch Comp Engn Ctr High Performance Embedded Syst Singapore 639798 Singapore

The collapsing knapsack problem (CKP) is a type of nonlinear knapsack problem in which the knapsack size is a non-increasing function of the number of items included. This paper proposes an exact algorithm for CKP by partitioning CKP to some subproblems, then solving them with the improved expanding-core technique. The proposed algorithm solves the subproblems in the special processing order resulting in the reduction of computing time. Experimental results show that the proposed algorithm is an efficient approach for various random instances of size up to 1000. (c) 2005 Elsevier Inc. All rights reserved.

关键词： collapsing knapsack problem 0-1 knapsack problem exact algorithm expanding-core

来源：评论

学校读者我要写书评

暂无评论

Partitioning graphs into connected parts

引用

THEORETICAL COMPUTER SCIENCE 2009年第47-49期410卷 4834-4843页

作者： van't Hof, Pim Paulusma, Daniel Woeginger, Gerhard J. Univ Durham Sci Labs Dept Comp Sci Durham DH1 3LE England Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands

The 2-DISJOINT CONNECTED SUBGRAPHS problem asks if a given graph has two vertex-disjoint connected subgraphs containing prespecified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The LONGEST PATH CONTRACTIBILITY problem asks for the largest integer l for which an input graph can be contracted to the path P-l on l vertices. We show that the computational complexity of the LONGEST PATH CONTRACTIBILITY problem restricted to P-l-free graphs jumps from being polynomially solvable to being NP-hard at l = 6, while this jump occurs at l = 5 for the 2-DISJOINT CONNECTED SUBGRAPHS problem. We also present an exact algorithm that solves the 2-DISJOINT CONNECTED SUBGRAPHS problem faster than O*(2(n)) for any n-vertex P-l-free graph. For l = 6, its running time is O*(1.5790(n)). We modify this algorithm to solve the LONGEST PATH CONTRACTIBILITY problem for PG-free graphs in O*(1.5790(n)) time. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Graph partition Edge contraction Path exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Resolution and linear CNF formulas: Improved (n, 3)-MAxSAT algorithms

引用

THEORETICAL COMPUTER SCIENCE 2019年 774卷 113-123页

作者： Xu, Chao Chen, Jianer Wang, Jianxin Cent S Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

We study techniques for solving the MAxSAT problem on instances in which the variable degree is bounded by 3. The problem is NP-hard. We show how resolution principle can be applied that converts an instance into an equivalent instance in which the CNF formula becomes a linear CNF formula. We then show how more efficient branching strategies can be applied on linear CNF formulas. As applications, we present two algorithms: one of running time O*(1.194(k)) that solves the parameterized version of the problem, and the other of running time O*(1.237(n)) that solves the optimization version of the problem, both significantly improving previous best upper bounds. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Maximum satisfiability Linear CNF formula Resolution principle Parameterized algorithm exact algorithm

来源：评论

学校读者我要写书评

暂无评论

On computing exact means of time series using the move-split-merge metric

引用

DATA MINING AND KNOWLEDGE DISCOVERY 2023年第2期37卷 595-626页

作者： Holznigenkemper, Jana Komusiewicz, Christian Seeger, Bernhard Univ Marburg Math & Comp Sci Marburg Germany

Computing an accurate mean of a set of time series is a critical task in applications like nearest-neighbor classification and clustering of time series. While there are many distance functions for time series, the most popular distance function used for the computation of time series means is the non-metric dynamic time warping (DTW) distance. A recent algorithm for the exact computation of a DTW-MEAN has a running time of O(n(2k+1)2(k)k), where k denotes the number of time series and n their maximum length. In this paper, we study the mean problem for the move-split-merge (MSM) metric that not only offers high practical accuracy for time series classification but also carries of the advantages of the metric properties that enable further diverse applications. The main contribution of this paper is an exact and efficient algorithm for the MSM-MEAN problem of time series. The running time of our algorithm is O(n(k+3)2(k)k(3)), and thus better than the previous DTW-based algorithm. The results of an experimental comparison confirm the running time superiority of our algorithm in comparison to the DTW-MEAN competitor. Moreover, we introduce a heuristic to improve the running time significantly without sacrificing much accuracy.

关键词： Time series means Time series metrics Dynamic programming exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Simple and Efficient Pattern Matching algorithms for Biological Sequences

引用

IEEE ACCESS 2020年 8卷 23838-23846页

作者： Neamatollahi, Peyman Hadi, Montassir Naghibzadeh, Mahmoud Ferdowsi Univ Mashhad Fac Engn Comp Engn Dept Mashhad *** Razavi Khorasan Iran

The remarkable growth of biological data is a motivation to accelerate the discovery of solutions in many domains of computational bioinformatics. In different phases of the computational pipelines, pattern matching is a very practical operation. For example, pattern matching enables users to find the locations of particular DNA subsequences in a database or DNA sequence. Furthermore, in these expanding biological databases, some patterns are updated over time. To perform faster searches, high-speed pattern matching algorithms are needed. The present paper introduces three pattern matching algorithms that are specially formulated to speed up searches on large DNA sequences. The proposed algorithms raise performance by utilizing word processing (in place of the character processing presented in previous works) and also by searching the least frequent word of the pattern in the sequence. In terms of time cost, the experimental results demonstrate the superiority of the presented algorithms over the other simulated algorithms.

关键词： Bioinformatics string matching DNA sequence frequent pattern exact algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：