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

SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION algorithmS

Parallel algorithms and Applications 1997年第3-4期10卷 271-281页

作者： Keqin Li - Phone: 914-257-3534. Fax: 914-463-1807. Email: lik@npvm.newpaltz.edu.[a] [a] Department of Mathematics and Computer Science State University of New York New Paltz New York USA

In this paper, we combine the techniques of approximation, parallelism, and randomization to solve the traveling salesman problem, one of the most celebrated problems in computer science. We show that there is an EREW PRAM algorithmA1such thatA1(l) ≤ 2 OPT(l) for all TSP instancesl, whereA1(l) is the length of the tour produced byA1, and OPT(l) is the length of an optimum tour. The algorithm has time complexityO(log2n), and usesO(n2) processors. There is a similar CREW PRAM algorithmA2that usesO(n2/log2n) processors. Furthermore, there is a Monte Carlo CREW PRAM algorithmA3which, for all TSP instancesl, finds a traveling salesman lour such thatA3(l) ≤ 1.5OPT(l) with probability at least 1 − (1/2k), wherekis any large integer. The randomized algorithm has time complexityO(log2n), and usesO(n5.5L) processors, whereLis the length of the interval which contains all distances inl. We also show that there is a Las Vegas CREW PRAM algorithmA4which, for all TSP instancesl, produces a traveling salesman tour such thatA4(l) ≤ 1.5 OPT(l), with expected time complexityO(log2n), and usingO(n5.5L) processors. Therefore, it is possible to accurately solve the TSP very fast with high probability by using a reasonable amount of resources.

关键词： Approximation algorithm parallel algorithm probabilistic algorithm traveling salesman

来源：评论

学校读者我要写书评

暂无评论

Steinhaus's geometric location problem for random samples in the plane

引用

Advances in Applied Probability 2016年第1期14卷 56-67页

作者： Dorit Hochbaum J. Michael Steele Carnegie-Mellon University Stanford University

Let where Xi, 1 ≦ i ≦ n, are i.i.d. and uniformly distributed in [0, 1]2. It is proved that Mn ∽ cn1–p/2 a.s. for 1 ≦ p <2. This result is motivated by recent developments in the theory of algorithms and the t... 详细信息

关键词： LOCATION PROBLEM k-MEDIAN PROBLEM probabilistic algorithm SUBADDITIVE PROCESS SUBADDITIVE EUCLIDEAN FUNCTIONAL

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT SCHEMES FOR PARALLEL COMMUNICATION

引用

JOURNAL OF THE ACM 1984年第3期31卷 507-517页

作者： UPFAL, E HEBREW UNIV JERUSALEM INST MATH & COMP SCIJERUSALEMISRAEL

A family of balanced communication schemes for connecting N processors with only a constant number of lines entering or leaving each processor is defined. It is proved that this network topology enables a fully distributed probabilistic algorithm to execute a variety of communication requests efficiently. In particular it enables implementation of an arbitrary permutation, that is, a set of N packets initially located in distinct processors and destined for distinct destinations in O(log//2N) steps. Similar results are proved for randomly generated communication requests. These results suggest an efficient solution to a fundamental problem in the design of parallel computers.

关键词： Network routing parallel computer probabilistic algorithm

来源：评论

学校读者我要写书评

暂无评论

A FINE ESTIMATE OF QUANTUM FACTORIZATION SUCCESS PROBABILITY

引用

INTERNATIONAL JOURNAL OF QUANTUM INFORMATION 2010年第8期8卷 1233-1238页

作者： Zawadzki, Piotr Silesian Tech Univ Dept Automat Control Elect & Comp Sci PL-44100 Gliwice Poland

The quantum algorithm for factorization is probably the most famous one in quantum computation. The algorithm succeeds only when some random number with an even order relative to the number to be factorized is fed as the input to the quantum order finding algorithm. It is well-known that numbers with even orders are found with probability not less than 1/2. In consequence, quantum device has to be used many times in the course of the factorization process to amplify the success probability. However, the above-mentioned limit is a rough estimate. Presented theoretical analysis and numerical simulation prove that the probability of finding a parameter with an even order is significantly higher for many composite numbers. It immediately follows that so far, presented analyses of factorization efficiency are highly underestimated in terms of required number of quantum device usage.

关键词： Quantum computation factorization probabilistic algorithm

来源：评论

学校读者我要写书评

暂无评论

Asymmetry of Strategies in Proposal: Gale-Shapley algorithm on Diagrams

引用

Procedia Computer Science 2016年 96卷 1730-1739页

作者： Yoshiteru Ishida Shigetaka Ikeno Department of Computer Science and Engineering Toyohashi University of Technology Tempaku Toyohashi 441-8580 Japan

This paper proposes a new diagram for a specific matching problem: the stable marriage problem. The diagram allows us to elicit not only the structure of with a blocking relation among the nodes representing pairs, but also asymmetry in the actions of the DA algorithm (Gale-Shapley algorithm). Symmetry and asymmetry of the stable marriage problems permit us to deduce strategies of whether or not and when proposals should be made. Some implications to the asymmetry in rewarding and penalty in the game theoretic model are also discussed.

关键词： diagram stable marriage problems probabilistic algorithm strategy decision making education model matching automaton

来源：评论

学校读者我要写书评

暂无评论

Information theoretic approach to complex biological network reconstruction: application to cytokine release in RAW 264.7 macrophages

引用

BMC SYSTEMS BIOLOGY 2014年第1期8卷 77页

作者： Farhangmehr, Farzaneh Maurya, Mano Ram Tartakovsky, Daniel M. Subramaniam, Shankar Univ Calif San Diego Dept Bioengn La Jolla CA 92093 USA Univ Calif San Diego Dept Mech & Aerosp Engn La Jolla CA 92093 USA Univ Calif San Diego San Diego Supercomputer Ctr La Jolla CA 92093 USA Univ Calif San Diego Dept Chem & Biochem Dept Cellular & Mol Med La Jolla CA 92093 USA Univ Calif San Diego Grad Program Bioinformat La Jolla CA 92093 USA

Background: High-throughput methods for biological measurements generate vast amounts of quantitative data, which necessitate the development of advanced approaches to data analysis to help understand the underlying mechanisms and networks. Reconstruction of biological networks from measured data of different components is a significant challenge in systems biology. Results: We use an information theoretic approach to reconstruct phosphoprotein-cytokine networks in RAW 264.7 macrophage cells. Cytokines are secreted upon activation of a wide range of regulatory signals transduced by the phosphoprotein network. Identifying these components can help identify regulatory modules responsible for the inflammatory phenotype. The information theoretic approach is based on estimation of mutual information of interactions by using kernel density estimators. Mutual information provides a measure of statistical dependencies between interacting components. Using the topology of the network derived, we develop a data-driven parsimonious input-output model of the phosphoprotein-cytokine network. Conclusions: We demonstrate the applicability of our information theoretic approach to reconstruction of biological networks. For the phosphoprotein-cytokine network, this approach not only captures most of the known signaling components involved in cytokine release but also predicts new signaling components involved in the release of cytokines. The results of this study are important for gaining a clear understanding of macrophage activation during the inflammation process.

关键词： Bioinformatics Data mining Network inference Data-driven network reconstruction Information theory Mutual information probabilistic algorithm Statistical methods

来源：评论

学校读者我要写书评

暂无评论

algorithms for Subset Sum Problem

International Journal of Electronics and Information Enginee...

引用

International Journal of Electronics and Information Engineering 2018年第2期9卷 106-114页

作者： Lihua Liu Lili Wang Zhengjun Cao Xiqi Wang

Given a set (or multiset) S of n numbers and a target number t, the subset sum problem is to decide if there is a subset of S that sums up to t. There are several methods for solving this problem, including exhaustive search, divide-and-conquer method, and Bellman's dynamic programming method. However, none of them could generate universal and light code. In this paper, we present a new deterministic algorithm based on a novel data arrangement, which could generate such code and return all solutions. If n is small enough, it is efficient for usual purpose. We also present a probabilistic version with one-sided error and a greedy algorithm which could generate a solution with minimized variance.

关键词： Deterministic algorithm Dynamic Programming Greedy algorithm Knapsack Problem probabilistic algorithm Subset Sum Problem

来源：评论

学校读者我要写书评

暂无评论

Vehicle routing and scheduling for regular mobile healthcare services 30

Vehicle routing and scheduling for regular mobile healthcare...

引用

30th IEEE International Conference on Tools with Artificial Intelligence (ICTAI)

作者： Pascaru, Cosmin Diac, Paul Alexandru Ioan Cuza Univ Dept Comp Sci Iasi Romania

ISBN: (纸本)9781538674499

We propose our solution to a particular practical problem in the domain of vehicle routing and scheduling. The generic task is finding the best allocation of the minimum number of mobile resources that can provide periodical services in remote locations. These mobile resources are based at a single central location. Specifications have been defined initially for a real life application that is the starting point of an ongoing project. Particularly, the goal is to mitigate health problems in rural areas around a city in Romania. Medically equipped vans are programmed to start daily routes from county capital, provide a given number of examinations in townships within the county and return to the capital city in the same day. From the health care perspective, each van is equipped with an ultrasound scanner, and they are scheduled to investigate pregnant woman each trimester aiming to diagnose potential problems. The project is motivated by reports currently ranking Romania as the country with the highest infant mortality rate in the European Union. We developed our solution in two phases: modeling of the most relevant parameters and data available for our goal and then design and implement an algorithm that provides an optimized solution. The most important metric of an output scheduling is the number of vans that are necessary to provide a given amount of examination time per township, followed by total travel time or fuel consumption, number of different routes, and others. Our solution implements two probabilistic algorithms out of which we chose the one that performs the best.

关键词： periodic vehicle routing multiple traveling salesmen crew scheduling healthcare infant mortality rate ultrasonography probabilistic algorithm heuristic genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

The Arizona IDMatcher: developing an identity matching tool for law enforcement 07

The Arizona IDMatcher: developing an identity matching tool ...

引用

Proceedings of the 8th annual international conference on Digital government research: bridging disciplines & domains

作者： G. Alan Wang Siddharth Kaza Shailesh Joshi Kris Chang Chunju Tseng Homa Atabakhsh Hsinchun Chen Virginia Polytechnic Institute and State University Blacksburg VA University of Arizona Tucson AZ

ISBN: (纸本)9781595935991

Identity resolution is central to fighting crime and terrorism. Identity information can be unreliable due to intentional deception or data entry errors. In this poster we propose to develop an efficient open-source entity-matching and identity resolution tool for law enforcement, based on a probabilistic matching technique that requires little or no human intervention in the matching process. Compared to the IBM Identity Resolution, the Arizona IDMatcher achieved better recall and overall F-measure ratings on two real-world datasets.

关键词： identity matching entity matching probabilistic algorithm

来源：评论

学校读者我要写书评

暂无评论

Dynamic Programming for Optimal Integration of Plug-in Hybrid Electric Vehicles (PHEVs) in Residential Electric Grid Areas

Dynamic Programming for Optimal Integration of Plug-in Hybri...

引用

Annual Conference on IEEE Industrial Electronics Society

作者： Harun TURKER Ahmad HABLY Seddik BACHA Grenoble Electrical Engineering Lab. Grenoble Image Parole Signal Automatique Lab.

ISBN: (纸本)9781467324199

Plug-in Hybrid Electric Vehicles (PHEVs) will strongly penetrate in the car fleet. Based on databases of the houses Daily Loads Profiles (DLPs) and on a probabilistic algorithm of PHEVs connections in residential electric grid areas, this paper determines the minimal charging current or PHEVs charging power which assures that the batteries reached the desired State of Charge (SOC) at the departure time without any charging restriction during peak hours. A dynamic optimization algorithm programming which defines an optimal constant charging current for the PHEV is developed. If charging occurs at home, the application of the proposed optimal algorithm on 10 000 cases shows statistically that a load power chargers for PHEVs charged in residential electric grid areas equals to 373W (230V×1.62A) ensures that 99.4% of the PHEVs batteries have a SOC equals to 100% for the next use.

关键词： Daily Load Profile Dynamic optimization algorithm Minimal charging current or power Optimal algorithm Plug-in Hybrid Electric Vehicle probabilistic algorithm Residential electric grid areas State of Charge

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：