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

An improved voting algorithm for planted (1,d) motif search

INFORMATION SCIENCES 2013年 237卷 305-312页

作者： Xu, Yun Yang, Jiaoyun Zhao, Yuzhong Shang, Yi Univ Sci & Technol China Dept Comp Sci Hefei 230026 Anhui Peoples R China Key Lab High Performance Comp Hefei 230026 Anhui Peoples R China Univ Missouri Dept Comp Sci Columbia MO USA

The planted motif search problem is a classical problem in bioinformatics that seeks to identify meaningful patterns in biological sequences. As an NP-complete problem, current algorithms focus on improving the average time complexity and solving challenging instances within an acceptable time. In this paper, we propose a new exact algorithm CVoting that improves the state-of-the-art Voting algorithm. CVoting uses a new hash technique to reduce the space complexity to O(mn + N(I,d)) and a new pruning technique to reduce the average time complexity to O(m2 nN(1, d)(1,). Experimental results show that CVoting outperforms competing algorithms, including PMS1, RISOTTO, Voting and Pmsprune, in both space and time: up to an order of magnitude faster and using less memory in solving challenging instances. The software of the proposed algorithm is publicly available at http://***. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Planted motif search exact algorithm Time and space complexity Challenging instances

来源：评论

学校读者我要写书评

暂无评论

exact and Approximate algorithms for Computing Betweenness Centrality in Directed Graphs

引用

FUNDAMENTA INFORMATICAE 2021年第3期182卷 219-242页

作者： Chehreghani, Mostafa Haghir Bifet, Albert Abdessalem, Talel Amirkabir Univ Technol Dept Comp Engn Tehran Polytech Tehran Iran Telecom Paris IP Paris LTCI Paris France

Graphs (networks) are an important tool to model data in different domains. Real-world graphs are usually directed, where the edges have a direction and they are not symmetric. Betweenness centrality is an important index widely used to analyze networks. In this paper, first given a directed network G and a vertex r is an element of V(G), we propose an exact algorithm to compute betweenness score of r. Our algorithm pre-computes a set RV(r), which is used to prune a huge amount of computations that do not contribute to the betweenness score of r. Time complexity of our algorithm depends on vertical bar RV(r)vertical bar and it is respectively Theta(vertical bar RV(r)vertical bar . vertical bar E(G)vertical bar) and Theta(vertical bar RV(r)vertical bar . vertical bar E(G)vertical bar + vertical bar RV(r)vertical bar . vertical bar V (G)vertical bar log vertical bar V (G)vertical bar) for unweighted graphs and weighted graphs with positive weights. jRV(r)j is bounded from above by vertical bar V (G)vertical bar - 1 and in most cases, it is a small constant. Then, for the cases where RV(r) is large, we present a simple randomized algorithm that samples from RV(r) and performs computations for only the sampled elements. We show that this algorithm provides an (epsilon, delta)-approximation to the betweenness score of r. Finally, we perform extensive experiments over several real-world datasets from different domains for several randomly chosen vertices as well as for the vertices with the highest betweenness scores. Our experiments reveal that for estimating betweenness score of a single vertex, our algorithm significantly outperforms the most efficient existing randomized algorithms, in terms of both running time and accuracy. Our experiments also reveal that our algorithm improves the existing algorithms when someone is interested in computing betweenness values of the vertices in a set whose cardinality is very small.

关键词： Social networks directed graphs betweenness centrality exact algorithm approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Applying Line Balancing to Improve Production Line Efficiency: A Case Study of an Automotive Company 13

Applying Line Balancing to Improve Production Line Efficienc...

引用

13th International Conference on Information Communication and Management (ICICM)

作者： Singhtaun, Chansiri Pipattanapoonsin, Veerawit Kasetsart Univ Dept Ind Engn Fac Engn Bangkok Thailand

ISBN: (纸本)9798400708114

This research aims to improve the efficiency of an automotive engine production line by reducing waiting waste caused by an unbalanced workload. Currently, there are 94 tasks allocated to 8 workstations. The cycle time of the bottleneck workstation, which is 167.60 seconds per unit, is higher than the takt time set at 87 seconds per unit. The tasks in the production line have been divided into 3 groups due to limitations in space and machinery. The tasks in each group will be balanced separately. The tasks in groups 1 and 3 can be arranged on the workstations to achieve a cycle time lower than the takt time, with the same number of workstations. To balance the assembly line in these groups, a mathematical model is used with the objective of minimizing cycle time under the constraint of a fixed number of workstations and a cycle time not exceeding the takt time. However, the other group does not consider the constraint of a cycle time lower than the takt time because the company does not want to increase the number of existing workstations, which is currently insufficient to meet this constraint. The Branch and Cut algorithm using the COIN-OR CBC library in OpenSolver is used to solve the mathematical models. The experimental results show that the production line balancing efficiency has improved for all groups, with an increase from 70.35% to 96.56% for group 1, an increase from 81.52% to 99.91% for group 2, and an increase from 90.42% to 98.92% for group 3. The lead time is reduced from 235.18 minutes to 198.51 minutes.

关键词： Lean Manufacturing Line Balancing Mathematical Model exact algorithm

来源：评论

学校读者我要写书评

暂无评论

SET PARTITIONING VIA INCLUSION-EXCLUSION

引用

SIAM JOURNAL ON COMPUTING 2009年第2期39卷 546-563页

作者： Bjorklund, Andreas Husfeldt, Thore Koivisto, Mikko Lund Univ Dept Comp Sci S-22100 Lund Sweden Aalto Univ Helsinki Inst Informat Technol Basic Res Unit FIN-00014 Helsinki Finland Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland

Given a set N with n elements and a family F of subsets, we show how to partition N into k such subsets in 2(n) n(O)(1) time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in 2(n) n(O)(1) time for several well-studied partition problems including domatic number, chromatic number, maximum k-cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is available, our algorithms run in time 3(n) n(O)(1) if membership in F can be decided in polynomial time. We solve chromatic number in O(2.2461(n)) time and domatic number in O(2.8718(n)) time. Finally, we present a family of polynomial space approximation algorithms that find a number between chi(G) and inverted right perpendicular(1 + epsilon)chi(G)inverted left perpendicular in time O(1.2209(n) + 2.2461(e-epsilon n)).

关键词： set partition graph coloring exact algorithm zeta transform inclusion-exclusion

来源：评论

学校读者我要写书评

暂无评论

Moderately exponential time algorithms for the maximum bounded-degree-1 set problem

引用

DISCRETE APPLIED MATHEMATICS 2018年 251卷 114-125页

作者： Chang, Maw-Shang Chen, Li-Hsuan Hung, Ling-Ju Liu, Yi-Zhi Rossmanith, Peter Sikdar, Somnath HungKuang Univ Dept Comp Sci & Informat Engn Taichung 43302 Taiwan AROBOT Innovat CO LTD New Taipei 235 Taiwan Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 62102 Taiwan Rhein Westfal TH Aachen Dept Comp Sci D-52056 Aachen Germany Natl Chung Cheng Univ Chiayi Taiwan HungKuang Univ Taichung Taiwan

A bounded-degree-1 set S in an undirected graph G = (V, E) is a vertex subset such that the maximum degree of G[S] is at most one. Given a graph G, the MAXIMUM BOUNDED-DEGREE-1 SET (MAX 1-BDS) problem is to find a bounded-degree-1 set S of maximum size in G. A notion related to bounded-degree sets is that of an s-plex used to define the cohesiveness of subgraphs in social networks. An s-plex S in a graph G = (V, E) is a vertex subset such that for each v is an element of S, deg(G[S])(v) >= vertical bar s vertical bar. One can easily show that a graph G has a 2-plex of size k iff the complement graph of G has a bounded-degree-1 set of size k. Both the MAXIMUM 2-PLEX problem and the MAXIMUM BOUNDED-DEGREE-1 SET problem are NP-hard. We give a simple branch-and-reduce algorithm running in polynomial space and applying branching strategies with at most three branches for MAX 1-BDS. We analyze the running time of the algorithm using measure-and-conquer and show that it runs in time O*(1.4613(n)) which is faster than previous exact algorithms. Moreover, we show that the MAx 1-BDS problem cannot be approximated to a ratio greater than n(is an element of-1) in polynomial time for all is an element of > 0 unless P = NP. Some moderately exponential time approximation algorithms are given for MAx 1-BDS and its dual problem. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Bounded-degree-1 set 2-plex Vertex cover P3 exact algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Scheduling about a given common due date to minimize mean squared deviation of completion times

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1996年第2期88卷 328-335页

作者： Weng, XH Ventura, JA PENN STATE UNIV DEPT IND & MANAGEMENT SYST ENGNUNIVERSITY PKPA 16802

In this paper the problem of minimizing the mean squared deviation (MSDP) of job completion times about a given common due date in n-job, single-machine scheduling is considered. The release times for all jobs are assumed to be zero. No polynomial time algorithms have been found to identify an optimal solution to MSDP. For the tightly restricted version of MSDP, no even pseudo-polynomial time algorithms have been found to identify an optimal solution. We present some dominance properties for MSDP based on which a pseudo-polynomial dynamic programming algorithm which is an extension of the dynamic programming algorithm proposed by Lee, Danusaputro and Lin is presented to optimally solve the tightly restricted version of MSDP. Computational results show that the proposed dynamic programming algorithm can optimally solve tightly restricted instances of MSDP with up to 100 jobs in less than two seconds.

关键词： production scheduling minimizing mean squared deviation dynamic programming exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Improving dynamic programming strategies for partitioning

引用

JOURNAL OF CLASSIFICATION 2004年第2期21卷 207-230页

作者： van Os, BJ Meulman, JJ Leiden Univ Dept Educ Studies Data Theory Grp NL-2300 RB Leiden Netherlands

Improvements to the dynamic programming (DP) strategy for partitioning (non-hierarchical classification) as discussed in Hubert, Arabie, and Meulman (2001) are proposed. First, it is shown how the number of evaluations in the DP process can be decreased without affecting generality. Both a completely nonredundant and a quasi-nonredundant method are proposed. Second, an efficient implementation of both approaches is discussed. This implementation is shown to have a dramatic increase in speed over the original program. The flexibility of the approach is illustrated by analyzing three data sets.

关键词： cluster analysis partitioning dynamic programming exact algorithm

来源：评论

学校读者我要写书评

暂无评论

On the implementation of LIR: the case of simple linear regression with interval data

引用

COMPUTATIONAL STATISTICS 2014年第3-4期29卷 743-767页

作者： Cattaneo, Marco E. G. V. Wiencierz, Andrea Ludwig Maximilians Univ Munchen Dept Stat D-80539 Munich Germany

This paper considers the problem of simple linear regression with interval-censored data. That is, pairs of intervals are observed instead of the pairs of precise values for the two variables (dependent and independent). Each of these intervals is closed but possibly unbounded, and contains the corresponding (unobserved) value of the dependent or independent variable. The goal of the regression is to describe the relationship between (the precise values of) these two variables by means of a linear function. Likelihood-based Imprecise Regression (LIR) is a recently introduced, very general approach to regression for imprecisely observed quantities. The result of a LIR analysis is in general set-valued: it consists of all regression functions that cannot be excluded on the basis of likelihood inference. These regression functions are said to be undominated. Since the interval data can be unbounded, a robust regression method is necessary. Hence, we consider the robust LIR method based on the minimization of the residuals' quantiles. For this method, we prove that the set of all the intercept-slope pairs corresponding to the undominated regression functions is the union of finitely many polygons. We give an exact algorithm for determining this set (i.e., for determining the set-valued result of the robust LIR analysis), and show that it has worst-case time complexity . We have implemented this exact algorithm as part of the R package linLIR.

关键词： Interval-censored data Nonparametric likelihood inference Robust regression Least median of squares exact algorithm R package

来源：评论

学校读者我要写书评

暂无评论

OPTIMIZATION OF VEHICLES ARRANGEMENT IN DISTRIBUTION CENTER

OPTIMIZATION OF VEHICLES ARRANGEMENT IN DISTRIBUTION CENTER

引用

1st International Conference on Logistics, Informatics and Service Science (LISS 2011)

作者： Yu, Jiang Qin, Yong Jia, Limin Xing, Zongyi Beijing Jiaotong Univ State Key Lab Rail Traff Control & Safety 3 Shang Yuan Cun Hai Dian Dist Beijing Peoples R China Nanjing Univ Sci & Technol Sch Mech Engn Nanjing Jiangsu Peoples R China

ISBN: (纸本)9789898425638

To solve the problem of low efficiency of vehicles arrangement in distribution center, this paper proposes an exact algorithm solution approach under the consideration of optimization algorithm of loading. First, a multi-objective optimization model of vehicles arrangement is established, then the linearity weighted method and the main objective method are used to convert the multi-objective optimization model into one-objective optimization model and is solved based on exact algorithm. The proposed method is applied to the distribution center management system by programming and the computational results shows the the effectiveness and performance of the method.

关键词： Distribution Center exact algorithm Vehicles Arrangement Multi-Objective Optimization Loading

来源：评论

学校读者我要写书评

暂无评论

exact SAMPLING OF DIFFUSIONS WITH A DISCONTINUITY IN THE DRIFT

引用

ADVANCES IN APPLIED PROBABILITY 2016年第A期48卷 249-259页

作者： Papaspiliopoulos, Omiros Roberts, Gareth O. Taylor, Kasia B. ICREA Barcelona Spain Univ Pompeu Fabra Dept Econ & Business Ramon Trias Fargas 25-27 Barcelona 08005 Spain Univ Warwick Dept Stat Coventry CV4 7AL W Midlands England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England

We introduce exact methods for the simulation of sample paths of one-dimensional diffusions with a discontinuity in the drift function. Our procedures require the simulation of finite-dimensional candidate draws from probability laws related to those of Brownian motion and its local time, and are based on the principle of retrospective rejection sampling. A simple illustration is provided.

关键词： exact algorithm sampling of diffusions diffusion with discontinuous drift retrospective rejection sampling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：