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

作者： Cai, Xingyu University of Connecticut

学位级别：Ph.D., Doctor of Philosophy

The Closest Pair problem aims to identify the closest pair (using some similarity measure, e.g., Euclidean distance, Dynamic Time Warping distance, etc.) of points in a metric space. This is one of the fundamental problems that has a wide range of applications in the data mining area, since most of the data can be represented in a vector form residing in a high dimensional space, and we would like to identify the relationship among those data points. Typical applications include but not limited to, social data analysis, user pattern identification, motif mining in biological data, data clustering, etc. This is a very classical problem and has been studied very well in the past *** this thesis, we study the Closest Pair problem and its variants, and also bring the machine learning perspective to solve some closely related problems. In particular, we have proposed two approximate algorithms to efficiently address the Closest Pair of Points (CPP) problem, and one deterministic approach to solve the Closest Pair of Subsequences (CPS) problem, using Euclidean distance measure. In addition, to identify the closest subsequences in the time series data, we have proposed a learnable feature extractor embedded in an artificial neural network, to learn patterns in the scope of the Dynamic Time Warping metric. In the end, to speed up the inference speed of the proposed algorithm, we have also proposed a neural network pruning technique to obtain a smaller network with similar *** the proposed methods are shown to have achieved the state-of-the-art performance in various standard benchmark datasets.

关键词： Closest Pair approximate algorithm Deterministic algorithm Dynamic Time Warping Neural Network

来源：评论

学校读者我要写书评

暂无评论

Minimize Maximum Coverage of Fragment Alignment Selection

Minimize Maximum Coverage of Fragment Alignment Selection

引用

2023 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2023

作者： Wang, Yuyang Jiang, Haitao Feng, Haodi Zhu, Daming Shandong University School of Computer Science and Technology Qingdao China

ISBN: (纸本)9798350337488

In genome/transcriptome assembly and similar scenarios, we are usually given millions of fragments and ready to assemble them into longer contigs by first aligning them to a reference sequence. Since one fragment may be aligned to different locations due to sequence repetition, mutation, and artificial factors the alignment tools concern, users of alignment tools must make their own strategies for choosing one location for each fragment. Commonly used strategies usually assign the same value for each location or assign values according to alignment scores without taking into account the optimization. Considering that a reasonable strategy should ensure that the coverage at each base is similar, we depict the problem of assigning fragments to properly aligned positions as an optimization problem that minimizes the maximum coverage over all bases, studying the computational complexities for some cases and designing polynomial-time or approximate polynomial-time algorithms for them and some others. © 2023 IEEE.

关键词： approximate algorithm Computational complexity Fragment alignment

来源：评论

学校读者我要写书评

暂无评论

An approximate calculation for error spectrum

An approximate calculation for error spectrum

引用

International Conference on Estimation, Detection and Information Fusion (ICEDIF)

作者： Weishi Peng Yangwang Fang Shaohua Chen School of Aeronautics and Astronautics Engineering Air Force Engineering University Xi'an Shaanxi China

ISBN: (纸本)9781479964192

As a comprehensive measure, the error spectrum will be widely used for estimation performance evaluation. However, it's hard to calculate without the error distribution. An approximate algorithm is proposed in this study to solve this problem. Then, how the approximate calculation can be used is illustrated by numerical examples. Finally, the correctness of the algorithm is validated by the simulation results.

关键词： approximate algorithm error spectrum estimation performance evaluation the law of large numbers approximate computation error distribution Spectra correctness of algorithm

来源：评论

学校读者我要写书评

暂无评论

PMS5: an efficient exact algorithm for the (l, d)-motif finding problem

引用

BMC BIOINFORMATICS 2011年第1期12卷 1-10页

作者： Dinh, Hieu Rajasekaran, Sanguthevar Kundeti, Vamsi K. Univ Connecticut Dept CSE Storrs CT 06269 USA

Background: Motifs are patterns found in biological sequences that are vital for understanding gene function, human disease, drug design, etc. They are helpful in finding transcriptional regulatory elements, transcription factor binding sites, and so on. As a result, the problem of identifying motifs is very crucial in biology. Results: Many facets of the motif search problem have been identified in the literature. One of them is (l, d)-motif search (or Planted Motif Search (PMS)). The PMS problem has been well investigated and shown to be NP-hard. Any algorithm for PMS that always finds all the (l, d)-motifs on a given input set is called an exact algorithm. In this paper we focus on exact algorithms only. All the known exact algorithms for PMS take exponential time in some of the underlying parameters in the worst case scenario. But it does not mean that we cannot design exact algorithms for solving practical instances within a reasonable amount of time. In this paper, we propose a fast algorithm that can solve the well-known challenging instances of PMS: (21, 8) and (23, 9). No prior exact algorithm could solve these instances. In particular, our proposed algorithm takes about 10 hours on the challenging instance (21, 8) and about 54 hours on the challenging instance (23, 9). The algorithm has been run on a single 2.4GHz PC with 3GB RAM. The implementation of PMS5 is freely available on the web at http://***/downloads/***. Conclusions: We present an efficient algorithm PMS5 that uses some novel ideas and combines them with well-known algorithm PMS1 and PMSPrune. PMS5 can tackle the large challenging instances (21, 8) and (23, 9). Therefore, we hope that PMS5 will help biologists discover longer motifs in the futures.

关键词： Integer Linear Program Exact algorithm approximate algorithm Input String Motif Search

来源：评论

学校读者我要写书评

暂无评论

Finding shortest gentle paths on polyhedral terrains by the method of multiple shooting

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2023年 67卷

作者： An, Phan Thanh Le, Nguyen Thi Trang, Le Hong Wong, Raymond Chi-Wing Ho Chi Minh City Univ Technol HCMUT IMACS Inst Math & Computat Sci 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 Linh Trung Ward Ho Chi Minh City Vietnam Vietnam Acad Sci & Technol VAST Inst Math 18 Hoang Quoc Viet Rd Hanoi Vietnam Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China

The problem of finding shortest 0-gentle paths can be stated as follows: given two points p, q on a polyhedral terrain and a slope parameter 0 e (0, n /2), the objective is to find a path joining p and q on the terrain which is shortest such that the slope of the path does not exceed 0. In this paper, we introduce some geometric and analysis properties of such paths and answer the question of whether known results of classical shortest paths hold for shortest 0-gentle paths. An algorithm for approximately computing such shortest 0-gentle paths on terrains is presented, where an approximate shortest 0-gentle path joining two points is a 0-gentle path whose length is the infimum of a sequence of that of 0-gentle paths in which they are decreasing. We also show that the sequence of lengths of paths obtained by the proposed algorithm is convergent. The algorithm is implemented in C++ using CGAL and Open GL in some specific circumstances.

关键词： approximate algorithm Geometric path constraints Method of multiple shooting Motion planning Shortest path Shortest gentle path Straightest geodesic

来源：评论

学校读者我要写书评

暂无评论

A model for the optimal number and locations of public distribution centers and its application to the Tokyo metoropolitan area

引用

INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING-THEORY APPLICATIONS AND PRACTICE 2002年第4期9卷 363-371页

作者： Yurimoto, S Katayama, N Ryutsu Keizai Univ Dept Econ Ibaraki 3018555 Japan Ryutsu Keizai Univ Dept Distribut & Logist Syst Ibaraki 3018555 Japan

In Japan, distribution centers managed by public authorities have been designed to achieve global optimization for efficient logistics and to maintain the Japanese urban environment. From the standpoint of social logistics, global optimization should be pursued considering both the environment and the efficiency of business logistics. In this study, we propose two nonlinear mathematical programming models for obtaining the optimal number and locations of public distribution centers and elaborate on the algorithm for determining solutions. These models aim at reducing the amount of truck CO2 emissions while minimizing logistics costs, which consist of transportation, delivery and facility operating costs. Our models are applied to the Tokyo metropolitan area. As the result of that, an appropriate policy for the number and locations of public distribution centers is proposed.

关键词： location public distribution center CO2 emissions mathematical programming approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Dynamic appointment scheduling with patient preferences and choices

引用

INDUSTRIAL MANAGEMENT & DATA SYSTEMS 2015年第4期115卷 700-717页

作者： Wang, Jin Fung, Richard Y. K. City Univ Hong Kong Dept Management Sci Hong Kong Hong Kong Peoples R China City Univ Hong Kong Dept Syst Engn & Engn Management Hong Kong Hong Kong Peoples R China

Purpose - The purpose of this paper is to maximize the expected revenue of the outpatient department considering patient preferences and choices. Design/methodology/approach - Patient preference refers to the preferred physician and time slot that patients hold before asking for appointments. Patient choice is the appointment decision the patient made after receiving a set of options from the scheduler. The relationship between patient choices and preferences is explored. A dynamic programming (DP) model is formulated to optimize appointment scheduling with patient preferences and choices. The DP model is transformed to an equivalent linear programming (LP) model. A decomposition method is proposed to eliminate the number of variables. A column generation algorithm is used to resolve computation problem of the resulting LP model. Findings - Numerical studies show the benefit of multiple options provided, and that the proposed algorithm is efficient and accurate. The effects of the booking horizon and arrival rates are studies. A policy about how to make use of the information of patient preferences is compared to other naive polices. Experiments show that more revenue can be expected if patient preferences and choices are considered. Originality/value - This paper proposes a framework for appointment scheduling problem in outpatient departments. It is concluded that more revenue can be achieved if more choices are provided for patients to choose from and patient preferences are considered. Additionally, an appointment decision can be made timely after receiving patient preference information. Therefore, the proposed model and policies are convenient tools applicable to an outpatient department.

关键词： Dynamic programming Appointment scheduling approximate algorithm Patient preferences

来源：评论

学校读者我要写书评

暂无评论

Multi-Batches Revenue Maximization for competitive products over online social network

引用

JOURNAL OF NETWORK AND COMPUTER APPLICATIONS 2022年 201卷 103357-103357页

作者： Liang, Guangxian Yao, Xiaopeng Gu, Yue Huang, Hejiao Gu, Chonglin Harbin Inst Technol Shenzhen Shenzhen Peoples R China

Enterprises can promote their products widely and rapidly over Online Social Network (OSN) through viral marketing. Viral marketing means an enterprise gives samples of one product to some individuals in OSN, such that the individuals promote the product to their fans and fans' fans. The information about the product diffuses virally over OSN, and enterprise gains great revenue from the sales. An enterprise which produces different types of products, called competitive products, should conduct viral marketing more than one batch to maximize revenue. Since each individual normally purchase one from different types, the earlier batch product occupies more customers than the later batch product. The enterprise should find a seed sets sequence for Multi-Batches Revenue Maximization (MBRM). In this paper, we observe the behavior of individuals promoting and purchasing products is independent, and propose a Multi-Batches Independent Cascade model. We comprehensively study how to select the seed sets sequence with adaptive method. Since MBRM combines Influence Maximization and integer knapsack problem, MBRM is NP-hard and needs to be optimally analyzed with dynamic programming method. We propose a computation framework with an approximation algorithm using price-aware Reach Reverse-set(p-RRset) and a heuristic algorithm. The experiments on four real OSN datasets show the efficiency and effectiveness of our algorithms.

关键词： Social networks Revenue maximization approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Just-in-time two-dimensional bin packing *

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2021年 102卷 102311-102311页

作者： Polyakovskiy, Sergey M'Hallah, Rym Deakin Univ Sch Informat Technol Geelong Vic 3216 Australia Kuwait Univ Coll Sci Dept Stat & Operat Res POB 5969 Safat 13060 Kuwait

This paper considers the on-time guillotine cutting of small rectangular items from large rectangular bins. Items assigned to a bin define the bins' processing time. Consequently, an item inherits the completion time of its assigned bin. Any deviation of an item's completion time from its due date causes either earliness or tardiness penalties. This just-in-time two-dimensional bin packing problem (JITBP) combines two difficult discrete optimization problems: Bin packing and total weighted earliness tardiness single machine scheduling. It is herein modeled as an integrated constraint program, augmented with two sets of logically redundant constraints that speed the search. The first set uses the concept of dual feasible functions. It focuses on bin packing feasibility. The second is the result of a linear program that schedules filled bins on a single machine. As an alternative to this integrated model, this paper proposes two decomposition cut-and-check approaches that define the master problem (MP) as a relaxation of JITBP where the items are reduced to dimensionless entities. They then reestablish the geometric feasibility of the MPs' solutions by iteratively augmenting MP with Benders cuts generated from the subproblems. The two approaches are similar in concept except that one implements MP as a constraint program (CP) while the second implements it as a mixed-integer program (MIP). Because JITBP is computationally challenging, we test all approaches under a number of heuristic assumptions, which include a maximum runtime for the MIP and CP solvers. The results provide computational evidence that the integrated constraint programming approach performs relatively well, and outperforms the decomposition approach whose MP is a CP. However, both approaches are outperformed by the decomposition approach whose MP is a warm-started MIP. (c) 2020 Elsevier Ltd. All rights reserved.

关键词： Weighted earliness tardiness Bin packing Scheduling Constraint programming Hybrid approach Branch-and-check approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient Resistance Distance Computation: The Power of Landmark-based Approaches

引用

Proceedings of the ACM on Management of Data 2023年第1期1卷 1-27页

作者： Meihao Liao Rong-Hua Li Qiangqiang Dai Hongyang Chen Hongchao Qin Guoren Wang Beijing Institute of Technology Beijing China Beijing Institute of Technology Zhejiang China

Resistance distance is a fundamental metric to measure the similarity between two nodes in graphs which has been widely used in many real-world applications. In this paper, we study two problems on approximately computing resistance distance: (i) single-pair query which aims at calculating the resistance distance r(s, t) for a given pair of nodes (s, t); and (ii) single-source query which is to compute all the resistance distances r(s, u) for all nodes u in the graph with a given source node s. Existing algorithms for these two resistance distance query problems are often costly on large graphs. To efficiently solve these problems, we first establish several interesting connections among resistance distance, a new concept called v-absorbed random walk, random spanning forests, and a newly-developed v-absorbed push procedure. Based on such new connections, we propose three novel and efficient sampling-based algorithms as well as a deterministic algorithm for single-pair query; and we develop an online and two index-based approximation algorithms for single-source query. We show that the two index-based algorithms for single-source query take almost the same running time as the algorithms for single-pair query with the aid of a linear-size index. The striking feature of all our algorithms is that they are allowed to select an easy-to-hit node by random walks on the graph. Such an easy-to-hit landmark node v can make the v-absorbed random walk sampling, spanning tree sampling, as well as the v-absorbed push more efficient, thus significantly improving the performance of our algorithms. Extensive experiments on 5 real-life datasets show that our algorithms substantially outperform the state-of-the-art algorithms for two resistance distance query problems in terms of both running time and estimation errors.

关键词： approximate algorithm graph proximity resistance distance

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：