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

Mathematical Model and Random Search algorithm for the Optimal Planning Problem of Replacing Traditional Public Transport with Electric

引用

AUTOMATION AND REMOTE CONTROL 2020年第5期81卷 803-818页

作者： Kovalyov, M. Y. Rozin, B. M. Guschinsky, N. N. Natl Acad Sci Belarus United Inst Informat Problems Minsk BELARUS

We investigate the complex optimization problem that arises in the planning of the transition process from traditional public transport to electric transport. We define the assumptions, input and output parameters of the problem, as well as its mathematical model and a randomized algorithm for solving it. We also give an extensive bibliography of publications on the problem at hand.

关键词： electric transport optimization mathematical programming randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Scheduling periodic messages on a shared link without buffering

引用

JOURNAL OF SCHEDULING 2024年第5期27卷 461-484页

作者： Guiraud, Mael Strozecki, Yann CESI Nanterre LINEACT BP 60293 Blvd Seine F-92006 Nanterre France Univ Versailles St Quentin DAVID Lab 45 Ave Etats Unis F-78000 Versailles France

Cloud RAN, a novel architecture for modern mobile networks, relocates processing units from antenna to distant data centers. This shift introduces the challenge of ensuring low latency for the periodic messages exchanged between antennas and their respective processing units. In this study, we tackle the problem of devising an efficient periodic message assignment scheme under the constraints of fixed message size and period without contention nor buffering. We address this problem by modeling it on a common network topology, wherein contention arises from a single shared link servicing multiple antennas. While reminiscent of coupled task scheduling, the introduction of periodicity adds a unique dimension to the problem. We study how the problem behaves with regard to the load of the shared link, and we focus on proving that, for load as high as possible, a solution always exists and it can be found in polynomial time. The main contributions of this article are two polynomial time algorithms, which find a solution for messages of any size and load at most 2/5 or for messages of size one and load at most phi-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi - 1$$\end{document}, the golden ratio conjugate. We also prove that a randomized greedy algorithm finds a solution on almost all instances with high probability, shedding light on the effectiveness of greedy algorithms in practical applications.

关键词： Periodic scheduling Greedy algorithm randomized algorithm Experimental algorithms C-RAN

来源：评论

学校读者我要写书评

暂无评论

Approximating the Canadian Traveller Problem with Online Randomization

引用

algorithmICA 2021年第5期83卷 1524-1543页

作者： Demaine, Erik D. Huang, Yamming Liao, Chung-Shou Sadakane, Kunihiko MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA Natl Tsing Hua Univ Dept Ind Engn & Engn Management Hsinchu 30013 Taiwan Univ Tokyo Dept Math Informat Tokyo Japan

In this paper, we study online algorithms for the Canadian Traveller Problem defined by Papadimitriou and Yannakakis in 1991. This problem involves a traveller who knows the entire road network in advance, and wishes to travel as quickly as possible from a source vertex s to a destination vertex t, but discovers online that some roads are blocked (e.g., by snow) once reaching them. Achieving a bounded competitive ratio for the problem is PSPACE-complete. Furthermore, if at most k roads can be blocked, the optimal competitive ratio for a deterministic online algorithm is 2k+1}, while the only randomized result known so far is a lower bound of k+1. We show, for the first time, that a polynomial time randomized algorithm can outperform the best deterministic algorithms when there are at least two blockages, and surpass the lower bound of 2k+1 by an o(1) factor. Moreover, we prove that the randomized algorithm can achieve a competitive ratio of (1+root 2/2)k + root 2 in pseudo-polynomial time. The proposed techniques can also be exploited to implicitly represent multiple near-shortest s-t paths.

关键词： Canadian traveller problem Competitive ratio randomized algorithm Next-to-shortest path Strictly ith-shortest path

来源：评论

学校读者我要写书评

暂无评论

Improved Parameterized Set Splitting algorithms: A Probabilistic Approach

引用

algorithmICA 2009年第4期54卷 472-489页

作者： Chen, Jianer Lu, Songjian Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

In this paper, we study parameterized algorithms for the set splitting problem, for both weighted and unweighted versions. First, we develop a new and effective technique based on a probabilistic method that allows us to develop a simpler and more efficient deterministic kernelization algorithm for the unweighted set splitting problem. We then propose a randomized algorithm for the weighted set splitting problem that is based on a new subset partition technique and has its running time bounded by O (*)(2 (k) ), which is significantly better than that of the previous best deterministic algorithm (which only works for the simpler unweighted set splitting problem) of running time O (*)(2.65 (k) ). We also show that our algorithm can be de-randomized, which leads to a deterministic parameterized algorithm of running time O (*)(4 (k) ) for the weighted set splitting problem and gives the first proof that the problem is fixed-parameter tractable.

关键词： Set splitting randomized algorithm Derandomization Parametrized algorithm

来源：评论

学校读者我要写书评

暂无评论

Mixed linear and semidefinite programming for combinatorial and quadratic optimization

引用

OPTIMIZATION METHODS & SOFTWARE 1999年第1-4期11-2卷 515-544页

作者： Benson, SJ Ye, YY Zhang, X Univ Iowa Iowa City IA 52242 USA Univ Iowa Dept Management Sci Iowa City IA 52242 USA Huazhong Univ Sci & Technol Sch Mech Engn Wuhan 430074 Peoples R China

We use the semidefinite relaxation to approximate combinatorial and quadratic optimization problems subject to linear, quadratic, as well as boolean constraints. We present a dual potential reduction algorithm and show how to exploit the sparse structure of various problems. Coupled with randomized and heuristic methods, we report computational results for approximating graph-partition and quadratic problems with dimensions 800 to 10,000. This finding, to the best of our knowledge, is the first computational evidence of the effectiveness of these approximation algorithms for solving large-scale problems.

关键词： semidefinite relaxation dual potential reduction algorithm maximum cut graph bisection bounded QP randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Motorcycle graphs and straight skeletons

引用

algorithmICA 2007年第2期47卷 159-182页

作者： Cheng, Siu-Wing Vigneron, Antoine Hong Kong Univ Sci & Technol Dept Comp Sci Kowloon Hong Kong Peoples R China INRA Unite Math & Informat Appl F-78352 Jouy En Josas France

We present a new algorithm to compute motorcycle graphs. It runs in O(n root n log n) time when n is the number of motorcycles. We give a new characterization of the straight skeleton of a nondegenerate polygon. For a polygon with n vertices and h holes, we show that it yields a randomized algorithm that reduces the straight skeleton computation to a motorcycle graph computation in expected O(n root n + 1 log(2) n) time. Combining these results, we can compute the straight skeleton of a nondegenerate polygon with h holes and with n vertices, among which r are reflex vertices, in O(n root n + 1 log(2) n + r root r log r) expected time. In particular, we can compute the straight skeleton of a nondegenerate polygon with n vertices in O(n root n log(2) n) expected time.

关键词： computational geometry randomized algorithm straight skeleton medial axis motorcycle graph

来源：评论

学校读者我要写书评

暂无评论

A different Deutsch-Jozsa

引用

QUANTUM INFORMATION PROCESSING 2015年第6期14卷 1777-1785页

作者： Bera, Debajyoti Indraprastha Inst Informat Technol IIIT D New Delhi 110020 India

One of the early achievements of quantum computing was demonstrated by Deutsch and Jozsa (Proc R Soc Lond A Math Phys Sci 439(1907):553, 1992) regarding classification of a particular type of Boolean functions. Their solution demonstrated an exponential speedup compared to classical approaches to the same problem;however, their solution was the only known quantum algorithm for that specific problem so far. This paper demonstrates another quantum algorithm for the same problem, with the same exponential advantage compared to classical algorithms. The novelty of this algorithm is the use of quantum amplitude amplification, a technique that is the key component of another celebrated quantum algorithm developed by Grover (Proceedings of the twenty-eighth annual ACM symposium on theory of computing, ACM Press, New York, 1996). A lower bound for randomized (classical) algorithms is also presented which establishes a sound gap between the effectiveness of our quantum algorithm and that of any randomized algorithm with similar efficiency.

关键词： Quantum algorithm Deutsch-Jozsa Amplitude amplification Lower bound randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Narrow passage sampling for probabilistic roadmap planning

引用

IEEE TRANSACTIONS ON ROBOTICS 2005年第6期21卷 1105-1115页

作者： Sun, Z Hsu, D Jiang, TT Kurniawati, H Reif, JH Hong Kong Baptist Univ Dept Comp Sci Kowloon Hong Kong Peoples R China Natl Univ Singapore Dept Comp Sci Singapore 117543 Singapore Duke Univ Dept Comp Sci Durham NC 27708 USA

Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but sampling narrow passages in a robot's configuration space remains a challenge for PRM planners. This paper presents a hybrid sampling strategy in the PRM framework for finding paths through narrow passages. A key ingredient of the new strategy is the bridge test, which reduces sample density in many unimportant parts of a configuration space, resulting in increased sample density in narrow passages. The bridge test can be implemented efficiently in high-dimensional configuration spaces using only simple tests of local geometry. The strengths of the bridge test and uniform sampling complement each other naturally. The two sampling strategies are combined to construct the hybrid sampling strategy for our planner. We implemented the planner and tested it on rigid and articulated robots in 2-D and 3-D environments. Experiments show that the hybrid sampling strategy enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages.

关键词： motion planning probabilistic roadmap (PRM) planner random sampling randomized algorithm robotics

来源：评论

学校读者我要写书评

暂无评论

Model Fitting Using RANSAC for Surgical Tool Localization in 3-D Ultrasound Images

引用

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING 2010年第8期57卷 1907-1916页

作者： Uhercik, Marian Kybic, Jan Liebgott, Herve Cachard, Christian Czech Tech Univ Dept Cybernet Fac Elect Engn CMP Prague 16627 Czech Republic Univ Lyon 1 CREATIS LRMN INSA Lyon INSERMCNRSUMR 5220U630 F-69622 Villeurbanne France

Ultrasound guidance is used for many surgical interventions such as biopsy and electrode insertion. We present a method to localize a thin surgical tool such as a biopsy needle or a microelectrode in a 3-D ultrasound image. The proposed method starts with thresholding and model fitting using random sample consensus for robust localization of the axis. Subsequent local optimization refines its position. Two different tool image models are presented: one is simple and fast and the second uses learned a priori information about the tool's voxel intensities and the background. Finally, the tip of the tool is localized by finding an intensity drop along the axis. The simulation study shows that our algorithm can localize the tool at nearly real-time speed, even using a MATLAB implementation, with accuracy better than 1 mm. In an experimental comparison with several alternative localization methods, our method appears to be the fastest and the most robust one. We also show the results on real 3-D ultrasound data from a PVA cryogel phantom, turkey breast, and breast biopsy.

关键词： Electrode localization needle 3-D ultrasound randomized algorithm random sample consensus (RANSAC) ultrasound guidance

来源：评论

学校读者我要写书评

暂无评论

The probabilistic approach to limited packings in graphs

引用

DISCRETE APPLIED MATHEMATICS 2015年 184卷 146-153页

作者： Gagarin, Andrei Zverovich, Vadim Univ London Dept Comp Sci Egham TW20 0EX Surrey England Univ W England Bristol BS16 1QY Avon England

We consider (closed neighbourhood) packings and their generalization in graphs. A vertex set X in a graph G is a k-limited packing if for every vertex v is an element of V (G), vertical bar N[v] boolean AND X vertical bar <= k, where N[v] is the closed neighbourhood of v. The k-limited packing number L-k(G) of a graph G is the largest size of a k-limited packing in G. Limited packing problems can be considered as secure facility location problems in networks. In this paper, we develop a new application of the probabilistic method to limited packings in graphs, resulting in lower bounds for the k-limited packing number and a randomized algorithm to find k-limited packings satisfying the bounds. In particular, we prove that for any graph G of order n with maximum vertex degree Delta. L-k(G) >= kn/(k+1) (k)root((Delta)(k)) (Delta+1) Also, some other upper and lower bounds for L-k (G) are given. (C) 2014 Elsevier B.V. All rights reserved.

关键词： k-limited packings The probabilistic method Lower and upper bounds randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：