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

deterministic normal position transformation and its applications

THEORETICAL COMPUTER SCIENCE 2020年 842卷 50-64页

作者： M-Alizadeh, Benyamin Hashemi, Amir Damghan Univ Sch Math & Comp Sci Damghan *** Iran Isfahan Univ Technol Dept Math Sci Esfahan *** Iran

In this paper, we address the problem of transforming an ideal into normal position. We present a deterministic algorithm (based on linear algebra techniques) that finds a suitable linear change of variables to transform a given zero-dimensional (not necessarily radical) ideal into normal position. The main idea of this algorithm is to achieve this position via a sequence of elementary linear changes;i.e. each change involves only two variables. Furthermore we give complete complexity analysis of all the algorithms described in this paper based on a sharp upper bound for the maximal number of required elementary linear changes in the special case of the bi-variate polynomial ideal. As an application of this investigation, we conclude the paper by giving a sharper complexity bound for computing a primary decomposition for a zero-dimensional ideal. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Polynomial ideals Grobner bases Normal position deterministic algorithm Shape lemma

来源：评论

学校读者我要写书评

暂无评论

deterministic 7/8-approximation for the metric maximum TSP

引用

THEORETICAL COMPUTER SCIENCE 2009年第47-49期410卷 5000-5009页

作者： Kowalik, Lukasz Mucha, Marcin Univ Warsaw Inst Informat PL-00913 Warsaw Poland

We present the first 7/8-approximation algorithm for the maximum Traveling Salesman Problem (MAX-TSP) with triangle inequality. Our algorithm is deterministic. This improves over both the randomized algorithm of Hassin and Rubinstein [R. Hassin, S. Rubinstein, A 7/8-approximation algorithm for metric Max TSP, Inf Process. Lett. 81 (5) (2002) 247-251] with an expected approximation ratio of 7/8 - O(n(-1/2)) and the deterministic (7/8 - O(n(-1/3)))-approximation algorithm of Chen and Nagoya [Z.-Z. Chen, T. Nagoya, Improved approximation algorithms for metric max TSP, in: Proc. ESA'05, 2005, pp. 179-190]. In the new algorithm, we extend the approach of processing local configurations using the so-called loose-ends. which we introduced in [L Kowalik, M. Mucha, 35/44-approximation for asymmetric maximum TSP with triangle inequality, in: Proc. 10th Workshop on algorithms and Data Structures, WADS'07, 2007, pp. 590-601]. (C) 2009 Elsevier B.V. All rights reserved.

关键词： The Traveling Salesman Problem Approximation deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

Towards efficiently searching triple product property triples: deterministic and randomized algorithms

引用

APPLIED SOFT COMPUTING 2019年 75卷 349-357页

作者： Chen, Zefeng Zhou, Yuren Xiang, Yi Guangzhou Coll South China Univ Technol Engn Res Inst Guangzhou 510800 Guangdong Peoples R China Sun Yat Sen Univ Sch Data & Comp Sci Guangzhou 510006 Guangdong Peoples R China South China Univ Technol Sch Software Engn Guangzhou 510006 Guangdong Peoples R China

The key objects in the group-theoretic approach to matrix multiplication are subsets of a group satisfying the so-called triple product property (TPP). In this paper, we focus on the problem of efficiently finding the triple product property triples. We deduce and present some new characteristics of the triple product property. Using these new characteristics, we firstly propose an efficient deterministic algorithm in which a screening process based on historical information is designed to reduce the search space. In contrast to some of the recent heuristic search methods, the proposed deterministic algorithm can search all kinds of TPP triples in a highly efficient way with the help of a novel representation for subsets and a Moving I principle. In addition, we also propose an efficient randomized algorithm for finding TPP triples, which adopts a greedy randomized strategy to randomly generate possible TPP candidates. Experimental results demonstrate that our proposed deterministic algorithm can achieve a huge speed-up in terms of running time compared with the existing deterministic algorithm, and the proposed randomized algorithm outperforms other existing approaches for finding TPP triples. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Matrix multiplication Triple product property deterministic algorithm Randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Coupling stochastic and deterministic local search in examination timetabling

引用

OPERATIONS RESEARCH 2007年第2期55卷 351-366页

作者： Caramia, Massimiliano Dell'Olmo, Paolo Univ Roma Tor Vergata Dipartimento Ingn Impresa I-00173 Rome Italy Univ Roma 1 Dipartimento Stat Probalitia & Stat Applicate I-00185 Rome Italy

In this paper, we propose a novel optimization algorithm for examination timetabling. It works by alternating two phases;one based on a stochastic local search and the other on a deterministic local search. The stochastic phase is fundamentally based on biased random sampling that iteratively constructs schedules according to a matrix whose entries are the probability with which exams can be assigned to time slots. The deterministic phase, instead, consists of assigning (according to a given ordering) each exam sequentially to the time slot that causes the lowest increase in the. schedule penalty. After a schedule is constructed, swap operations are executed to improve performance. These two phases are coupled and made closely interactive by tunnelling information on what has happened during one phase to the successive ones. Moreover, the length of a phase and the parameter framework to be used in a new phase are automatically determined by a record of the process. We tested the proposed technique on known benchmarks, and a comparison with 17 algorithms drawn from the state of the art appears to show that our algorithm is able to improve best-known results. In particular, in reference to uncapacitated problems, i.e., the ones without room constraints, our algorithm bested the state of the art in 70% to 90% of the tested instances, while in capacitated problems with overnight conflicts (second-order conflicts), it was superior to all the other algorithms.

关键词： scheduling heuristic deterministic algorithm stochastic algorithm biasedrandom sampling examination timetabling local search

来源：评论

学校读者我要写书评

暂无评论

deterministic model for the transport of energetic particles: Application in the electron radiotherapy

引用

PHYSICA MEDICA-EUROPEAN JOURNAL OF MEDICAL PHYSICS 2015年第8期31卷 912-921页

作者： Caron, J. Feugeas, J. -L. Dubroca, B. Kantor, G. Dejean, C. Birindelli, G. Pichard, T. Nicolai, P. d'Humieres, E. Frank, M. Tikhonchuk, V. Univ Bordeaux CNRS CEA CELIA Ctr Lasers Intenses & Applicat F-33400 Talence France Inst Bergonie Ctr Comprehens Canc Dept Radiotherapy F-33076 Bordeaux France Ctr Antoine Lacassagne Ctr Comprehens Canc Dept Radiotherapy F-06000 Nice France Rhein Westfal TH Aachen Ctr Engn Computat Sci Dept Math Aachen Germany

A new deterministic method for calculating the dose distribution in the electron radiotherapy field is presented. The aim of this work was to validate our model by comparing it with the Monte Carlo simulation toolkit, GEANT4. A comparison of the longitudinal and transverse dose deposition profiles and electron distributions in homogeneous water phantoms showed a good accuracy of our model for electron transport, while reducing the calculation time by a factor of 50. Although the Bremsstrahlung effect is not yet implemented in our model, we propose here a method that solves the Boltzmann kinetic equation and provides a viable and efficient alternative to the expensive Monte Carlo modeling. (C) 2015 Associazione Italiana di Fisica Medica. Published by Elsevier Ltd. All rights reserved.

关键词： Radiotherapy treatment planning system deterministic algorithm Electron dosimetry Monte Carlo algorithm

来源：评论

学校读者我要写书评

暂无评论

deterministic M2M multicast in radio networks

引用

THEORETICAL COMPUTER SCIENCE 2006年第1-3期362卷 196-206页

作者： Gasieniec, Leszek Kranakis, Evangelos Pelc, Andrzej Xin, Qin Univ Liverpool Dept Comp Sci Liverpool L69 7ZF Merseyside England Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Univ Quebec Dept Informat Gatineau PQ J8X 3X7 Canada Univ Bergen Dept Informat N-5020 Bergen Norway

We study the problem of exchanging messages within a fixed group of k nodes, called participants, in an n-node radio network, modeled as an undirected graph. This communication task was previously considered in the setting of ATM video applications, in [J.M. Tsai, H.-H. Fang, C.-Y. Lee, A multicast solution for ATM video applications, IEEE Trans. Circuits Systems Video Technol. 7 (1997) 675-686], and was called multipoint-to-multipoint (M2M) multicasting. While the radio network topology is known to all nodes, it is assumed that no node is aware of the location of the participants. We give a distributed deterministic algorithm for the M2M multicasting problem in radio networks, and analyze its time complexity. We show that if the maximum distance between any two out of k participants is d then this local information exchange problem can be solved in time O(d log(2) n + k log(4) n). (C) 2006 Elsevier B.V. All rights reserved.

关键词： radio communication deterministic algorithm broadcasting multicasting

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time deterministic approach to the travelling salesperson problem

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2020年第4期35卷 454-460页

作者： Jazayeri, Ali Sayama, Hiroki Drexel Univ Coll Comp & Informat Philadelphia PA 19104 USA SUNY Binghamton Dept Syst Sci & Ind Engn Binghamton NY USA

We propose a new polynomial-time deterministic algorithm that produces an approximated solution for the travelling salesperson problem. The proposed algorithm ranks cities based on their priorities calculated using a power function of means and standard deviations of their distances from other cities and then connects the cities to their neighbours in the order of their priorities. When connecting a city, a neighbour is selected based on their neighbours' priorities calculated as another power function that additionally includes their distance from the focal city to be connected. This repeats until all the cities are connected into a single loop. The time complexity of the proposed algorithm is O(n(2)), where n is the number of cities. Numerical evaluation shows that, despite its simplicity, the proposed algorithm produces shorter tours with less time complexity than other conventional tour construction heuristics. The proposed algorithm can be used by itself or as an initial tour generator for other more complex heuristic optimisation algorithms.

关键词： Travelling salesperson problem polynomial-time algorithm deterministic algorithm approximation

来源：评论

学校读者我要写书评

暂无评论

deterministic distinct-degree factorization of polynomials over finite fields

引用

JOURNAL OF SYMBOLIC COMPUTATION 2004年第6期38卷 1461-1470页

作者： Gao, SH Kaltofen, E Lauder, AGB N Carolina State Univ Dept Math Raleigh NC 27695 USA Clemson Univ Dept Math Sci Clemson SC 29634 USA Univ Oxford Inst Math Oxford OX1 3LB England

A deterministic polynomial time algorithm is presented for finding the distinct-degree factorization of multivariate polynomials over finite fields. As a consequence, one can count the number of irreducible factors of polynomials over finite fields in deterministic polynomial time, thus resolving a theoretical open problem of Kaltofen from 1987. (C) 2004 Elsevier Ltd. All rights reserved.

关键词： multivariate polynomial deterministic algorithm distinct-degree factorization

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: deterministic Massively Parallel algorithms for Ruling Sets 22

Brief Announcement: Deterministic Massively Parallel Algorit...

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Pai, Shreyas Pemmaraju, Sriram V. Aalto Univ Espoo Finland Univ Iowa Iowa City IA USA

ISBN: (纸本)9781450392624

In this paper we present a deterministic O( log logn)-round algorithm for the 2-ruling set problem in the Massively Parallel Computation (MPC) model with O-similar to (n) memory;this algorithm also runs in O( log logn) rounds in the Congested Clique model. This is exponentially faster than the fastest known deterministic 2-ruling set algorithm for these models, which is simply the Omicron(log Delta)-round deterministic Maximal Independent Set (MIS) algorithm due to Czumaj, Davies, and Parter (SPAA 2020). Our result is obtained by derandomizing the 2-ruling set algorithm of Kothapalli and Pemmaraju (FSTTCS 2012).

关键词： Ruling Sets Massively Parallel Computing Congested Clique deterministic algorithm Derandomization

来源：评论

学校读者我要写书评

暂无评论

Time Versus Cost Tradeoffs for deterministic Rendezvous in Networks 14

Time Versus Cost Tradeoffs for Deterministic Rendezvous in N...

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Miller, Avery Pelc, Andrzej Univ Quebec Outaouais Gatineau PQ Canada

ISBN: (纸本)9781450329446

Two mobile agents, starting from different nodes of a network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds using a deterministic algorithm. In each round, an agent decides to either remain idle or to move to one of the adjacent nodes. Each agent has a distinct integer label from the set {1,...,L}, which it can use in the execution of the algorithm, but it does not know the label of the other agent. Two main efficiency measures of a rendezvous algorithm's performance are its time (the number of rounds until the meeting) and its cost (the combined number of edge traversals by both agents). We investigate tradeoffs between these two measures. A natural benchmark for both time and cost of rendezvous in a network is the number of edge traversals needed for visiting all nodes of the network, called the exploration time. Indeed, this is a lower bound on both the time and the cost of rendezvous. Hence we express the time and cost of rendezvous as functions of an upper bound E on the time of exploration (known to both agents) and the size L of the label space. We present two natural rendezvous algorithms. algorithm Cheap has cost O(E) (and, in fact, a version of this algorithm for the model where the agents start simultaneously has cost exactly E) and time O(EL). algorithm Fast has both time and cost O(E log L). Our main contributions are lower bounds showing that, perhaps surprisingly, these two algorithms capture the tradeoffs between time and cost of rendezvous almost tightly. We show that any rendezvous algorithm of cost asymptotically E (i.e., of cost E+o(E)) must have time Omega(EL). On the other hand, we show that any rendezvous algorithm with time complexity O(E log L) must have cost Omega(E log L). Moreover, while our algorithms work for arbitrary connected graphs and arbitrary starting times of the agents, these lower bounds hold even in a scenario that is very favorable for poten

关键词： rendezvous deterministic algorithm mobile agent cost time.

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：