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

Minimum-width annulus with outliers: Circular, square, and rectangular cases

INFORMATION PROCESSING LETTERS 2019年 145卷 16-23页

作者： Ahn, Hee-Kap Ahn, Taehoon Bae, Sang Won Choi, Jongmin Kim, Mincheol Oh, Eunjin Shin, Chan-Su Yoon, Sang Duk POSTECH Dept Comp Sci & Engn Pohang South Korea Kyonggi Univ Div Comp Sci & Engn Suwon South Korea Max Planck Inst Informat Saarbrucken Germany Hankuk Univ Foreign Studies Div Comp & Elect Syst Engn Seoul South Korea Samsung Display Co Ltd Yongin South Korea

We study the problem of computing a minimum-width annulus with outliers. Specifically, given a set of n points in the plane and an integer k with 1 <= k <= n, the problem asks to find a minimum-width annulus that contains at least n - k input points. The k excluded points are considered as outliers of the input points. In this paper, we are interested in particular in annuli of three different shapes: circular, square, and rectangular annuli. For the three cases, we present first and improved algorithms to the problem. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Computational geometry Geometric shape matching exact algorithm Annulus Outlier

来源：评论

学校读者我要写书评

暂无评论

On the two-dimensional knapsack problem

引用

OPERATIONS RESEARCH LETTERS 2004年第1期32卷 5-14页

作者： Caprara, A Monaci, M Univ Bologna Dipartimento Elettr Informat & Sistemist I-40136 Bologna Italy

We address the two-dimensional Knapsack Problem (2YP), aimed at packing a maximum-profit subset of rectangles selected from a given set into another rectangle. We consider the natural relaxation of 2KP given by the one-dimensional KP with item weights equal to the rectangle areas, proving the worst-case performance of the associated upper bound, and present and compare computationally four exact algorithms based on the above relaxation, showing their effectiveness. (C) 2003 Elsevier B.V. All rights reserved.

关键词： two-dimensional knapsack upper bound approximation algorithm worst-case performance exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficiently computing geodesic offsets on triangle meshes by the extended Xin-Wang algorithm

引用

COMPUTER-AIDED DESIGN 2011年第11期43卷 1468-1476页

作者： Xin, Shi-Qing Ying, Xiang He, Ying Nanyang Technol Univ Sch Comp Engn Singapore Singapore

Geodesic offset curves are important for many industrial applications, such as solid modeling, robot-path planning, the generation of tool paths for NC machining, etc. Although the offset problem is well studied in classical differential geometry and computer-aided design, where the underlying surface is sufficiently smooth, very few algorithms are available for computing geodesic offsets on discrete representation, in which the input is typically a polyline curve restricted on a piecewise linear mesh. In this paper, we propose an efficient and exact algorithm to compute the geodesic offsets on triangle meshes by extending the Xin-Wang algorithm of discrete geodesics. We define a new data structure called parallel-source windows, and extend both the "one angle one split" and the filtering theorem to maintain the window tree. Similar to the original Xin-Wang algorithm, our extended algorithm has an O(n) space complexity and an O(n(2) log n) asymptotic time complexity, where n is the number of vertices on the input mesh. We tested our algorithm on numerous real-world models and showed that our algorithm is exact, efficient and robust, and can be applied to large scale models with complicated geometry and topology. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Discrete geodesics Geodesic offsets Geodesic distance field exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Fault-tolerant tile mining

引用

EXPERT SYSTEMS WITH APPLICATIONS 2018年 101卷 25-42页

作者： Lu, Haibing Zhu, Wendong Phan, Joseph Ghiassi, M. Fang, Yi Hong, Yuan He, Xiaoyun Santa Clara Univ Dept Operat Management & Informat Syst Santa Clara CA 95053 USA Global Energy Interconnect Res Inst North Amer Santa Clara CA USA Santa Clara Univ Dept Comp Engn Santa Clara CA 95053 USA Santa Clara Univ Dept Operat Management & Informat Syst Santa Clara CA 95053 USA IIT Dept Comp Sci Chicago IL 60616 USA Auburn Univ Dept Informat Syst Montgomery AL 36117 USA

Interesting itemset mining is a fundamental research problem in knowledge management and machine learning. It is intended to identify interesting relations between variables in a database using some measures of interestingness and has a number of applications, including market basket analysis, web usage mining, intrusion detection, and many others. This paper proposes a new interestingness measure, the fault-tolerant tile. That is based on two observations: (1) the length of an itemset can be as important as its frequency;(2) knowledge discovery from real-world datasets calls for fault -tolerant data mining (e.g. extracting fault -tolerant association rules, analyzing noisy datasets). Given a user-defined fault tolerance value, we are interested in finding the maximum/top-k fault-tolerant tiles. Due to the exponential search space of candidate itemsets, both problems are NP-hard. While using some monotonic property to prune search space is a common strategy for interesting itemset mining, no monotonic property is available for this problem. To tackle the challenge, we utilize the branch-and-bound search strategy to analyze the characteristics of candidate itemsets at each searching branch and estimating their bounds. Our experimental results show that our algorithms can effectively analyze real datasets and retrieve meaningful results. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Itemset mining Fault-tolerant Optimization exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved worst-case complexity for the MIN 3-SET COVERING problem

引用

OPERATIONS RESEARCH LETTERS 2007年第2期35卷 205-210页

作者： Della Croce, Federico Escoffier, Bruno Paschos, Vangelis Th. CNRS LAMSADE UMR 7024 F-75775 Paris 16 France Univ Paris 09 F-75775 Paris 16 France Politecn Turin DAI Turin Italy

We consider MIN SET COVERING when the subsets are constrained to have maximum cardinality 3. We propose an exact algorithm whose worst-case complexity is bounded above by O*(1.3957(m)) where in is the number of sets in the instance. This result improves upon the previously known bound of O*(1.4391(m)). (c) 2006 Elsevier B.V. All rights reserved.

关键词： worst-case complexity exact algorithm MIN SET COVERING

来源：评论

学校读者我要写书评

暂无评论

Line-seru conversion towards reducing worker(s) without increasing makespan: models, exact and meta-heuristic solutions

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2017年第10期55卷 2990-3007页

作者： Yu, Yang Sun, Wei Tang, Jiafu Kaku, Ikou Wang, Junwei Northeastern Univ Inst Syst Engn Shenyang Peoples R China Univ Hong Kong Dept Ind & Mfg Syst Engn Hong Kong Hong Kong Peoples R China Liaoning Univ Coll Business Adm Shenyang Peoples R China Dongbei Univ Finance & Econ Coll Management Sci & Engn Dalian Peoples R China Tokyo City Univ Fac Environm & Informat Studies Tokyo Japan

Compared with the traditional assembly line, seru production can reduce worker(s) and decrease makespan. However, when the two objectives are considered simultaneously, Pareto-optimal solutions may save manpower but increase makespan. Therefore, we formulate line-seru conversion towards reducing worker(s) without increasing makespan and develop exact and meta-heuristic algorithms for the different scale instances. Firstly, we analyse the distinct features of the model. Furthermore, according to the feature of the solution space, we propose two exact algorithms to solve the small to medium-scale instances. The first exact algorithm searches the solution space from more workers to fewer workers. The second exact algorithm searches the solution space from fewer workers to more workers. The two exact algorithms search a part of solution space to obtain the optimal solution of reducing worker(s) without increasing makespan. According to the variable length of the feasible solutions, we propose a variable-length encoding heuristic algorithm for the large-scale instances. Finally, we use the extensive experiments to evaluate the performance of the proposed algorithms and to investigate some managerial insights on when and how to reduce worker(s) without increasing makespan by line-seru conversion.

关键词： Seru production reducing worker(s) without increasing makespan exact algorithm variable-length encoding

来源：评论

学校读者我要写书评

暂无评论

On fast enumeration of maximal cliques in large graphs

引用

EXPERT SYSTEMS WITH APPLICATIONS 2022年第0期187卷 115915-115915页

作者： Jin, Yan Xiong, Bowen He, Kun Zhou, Yangming Zhou, Yi Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan Peoples R China East China Univ Sci & Technol Sch Informat Sci & Engn Shanghai Peoples R China Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

Maximal Clique Enumeration (MCE) is a fundamental and challenging problem in graph theory and various network applications. Numerous algorithms have been proposed in the past decades, however, only a few of them focus on improving the practical efficiency in large graphs. To this end, we propose an efficient algorithm called FACEN based on the Bron-Kerbosch framework. To optimize the memory and time consumption, we apply a hybrid data structure with adjacency list and partial adjacency matrix, and introduce a dynamic pivot selection rule based on the degeneracy order. FACEN is evaluated on a total of 64 benchmark instances from various sources. Computational results indicate that the proposed algorithm is highly competitive with the current leading MCE methods. In particular, our algorithm is able to enumerate all maximal cliques on the tested real-world social networks with millions of vertices and edges. For very large graphs, we provide an additional experiment for solving the MCE variant with lower bound, and investigate the benefits of FACEN.

关键词： Maximal clique enumeration exact algorithm NP-hard Bron-Kerbosch algorithm Social network

来源：评论

学校读者我要写书评

暂无评论

An iterative dynamic programming approach for the temporal knapsack problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第2期293卷 442-456页

作者： Clautiaux, F. Detienne, B. Guillot, G. Univ Bordeaux UMR CNRS 5251 Inria Bordeaux Sud Ouest Bordeaux France

In this paper, we address the temporal knapsack problem (TKP), a generalization of the classical knapsack problem, where selected items enter and leave the knapsack at fixed dates. We model the TKP with a dynamic program of exponential size, which is solved using a method called Successive Sublimation Dynamic Programming (SSDP). This method starts by relaxing a set of constraints from the initial problem, and iteratively reintroduces them when needed. We show that a direct application of SSDP to the temporal knapsack problem does not lead to an effective method, and that several improvements are needed to compete with the best results from the literature. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Temporal knapsack exact algorithm Lagrangian relaxation Successive sublimation dynamic programming method

来源：评论

学校读者我要写书评

暂无评论

Finding globally shortest paths through a sequence of adjacent triangles by the method of orienting curves

引用

JOURNAL OF GLOBAL OPTIMIZATION 2023年第4期85卷 1037-1063页

作者： Phan Thanh An Hoang Xuan Phu Ho Chi Minh City Univ Technol HCMUT Inst Math & Computat Sci IMACS 268 Ly Thuong Kiet StDist 10 Ho Chi Minh City Vietnam Ho Chi Minh City Univ Technol HCMUT Fac Appl Sci 268 Ly Thuong Kiet StDist 10 Ho Chi Minh City Vietnam Vietnam Natl Univ Ho Chi Minh City Ho Chi Minh City Vietnam Vietnam Acad Sci & Technol Inst Math 18 Hoang Quoc Viet Rd Hanoi Vietnam

In this paper, an exact algorithm based on the method of orienting curves is developed for solving the convex non-differentiable optimization problem on the closed unit cube in a finite dimensional space: finding the shortest path joining two points going through a sequence of adjacent triangles in 3D. As a result, the global solution of the problem is determined successively by some orienting curves and final curve, which can be exactly constructed with ruler and compass. A detailed numerical example is presented.

关键词： Convex non-differentiable optimization exact algorithm Global solution Path planning Planar unfolding Polyhedral surface Polytope Shortest path Straightest geodesic

来源：评论

学校读者我要写书评

暂无评论

Invariance relations for random walks on simple cubic lattices

引用

CHEMICAL PHYSICS LETTERS 2006年第1-3期421卷 287-294页

作者： Garza-López, RA Linares, A Yoo, A Evans, G Kozak, JJ Pomona Coll Dept Chem Claremont CA 91711 USA CALTECH Beckman Inst Pasadena CA 91125 USA

In recent work, we have built upon seminal contributions of Montroll and Weiss to develop invariance relations for random walks on k = 2 hexagonal and square-planar lattices. In this study, we extend our approach to determine invariance relations for random walks on k = 3 finite, simple cubic lattices subject to periodic boundary conditions. Use of these invariance relations allows one to calculate estimates of the overall mean walklength before trapping, and we show that the results obtained are in excellent agreement with numerically-exact calculated values. The results and analysis presented here yield insights on the problem of self-avoiding walks on cubic lattices. (c) 2006 Elsevier B.V. All rights reserved.

关键词： D-DIMENSIONAL WALKS DIFFUSION-CONTROLLED REACTIONS INFINITE LATTICES exact algorithm FINITE TRAPS EFFICIENCY Finite invariance cubic lattices Random walk reaction control

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：