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

21st annual acm/siam symposium on discrete algorithms

作者： Czyzowicz, Jurek Labourel, Arnaud Pelc, Andrzej Univ Quebec Outaouais Dept Informat Gatineau PQ J8X 3X7 Canada

ISBN: (纸本)9780898717013

Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment the actual walk of each agent also depends on an asynchronous adversary that, may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent m each segment of its route is continuous, does not leave it and covers all of it Meeting in a graph means that, both agents must be at the same tune in some node or in some point inside an edge of the graph, while meeting in a terrain am means that both agents must be at the saute time in some point of the terrain Does time exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerful adversary? We give deterministic rendezvous algorithms rot agents starting at arbitrary nodes of any anonymous connected graph (finite on infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior While our algorithms work in a very general setting - agents can, indeed. meet. almost, everywhere - we show that, none of the above few limitations imposed on the environment can be removed On the other hand our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary ulterior points of a terrain as above, agents will eventually get at an arbitrarily small positive distance from each other

关键词： Landforms

来源：评论

学校读者我要写书评

暂无评论

Asymmetric Traveling Salesman Path and Directed Latency Problems

Asymmetric Traveling Salesman Path and Directed Latency Prob...

引用

21st annual acm/siam symposium on discrete algorithms

作者： Friggstad, Zachary Salavatipour, Mohammad R. Svitkina, Zoya Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

ISBN: (纸本)9780898717013

We study integrality gaps and approximability of two closely related problems on directed graphs. Given a set V of n nodes in an underlying asymmetric metric and two specified nodes s and t, both problems ask to find an s-t path visiting all other nodes In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total cost of this path. In the directed latency problem, the objective is to minimize the sum of distances on this path from s to each node. Both of these problems are NP-hard the best known approximation algorithms for ATSPP had ratio O(log n) [7,9] until the very recent result that improves it to O(log n/ log log n) [3,9]. However, only a bound of O(root n) for the integrality gap of its lineal programming relaxation has been known. For directed latency, the best previously known approximation algorithm has a guarantee of O(n(1/2+epsilon)), for any constant epsilon > 0 [23] We present a new algorithm for the ATSPP problem that has approximation ratio of O(log n), but whose analysis also bounds the integrality gap of the standard LP relaxation of ATSPP by the same factor. this solves an open problem posed in [7]. We then pursue a deeper study of this LP and its variations and their use in approximating directed latency. Our second major result is an O(log n)approximation to the directed latency problem this also places an O(log n) bound on the integrality gap of a new LP relaxation of the latency problem that we introduce

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Asynchronous Byzantine Agreement and Leader Election with Full Information

Fast Asynchronous Byzantine Agreement and Leader Election wi...

引用

19th annual acm-siam symposium on discrete algorithms (SODA)

作者： Kapron, Bruce M. Kempe, David King, Valerie Saia, Jared Sanwalani, Vishal Univ Victoria Dept Comp Sci Victoria BC V8W 2Y2 Canada Univ So Calif Dept Comp Sci Los Angeles CA 90089 USA Univ Victoria Dept Comp Sci Victoria BC V8W 3P6 Canada Univ New Mexico Dept Comp Sci Albuquerque NM 87131 USA

We resolve two long-standing open problems in distributed computation by describing polylogarithmic protocols for Byzantine agreement and leader election in the asynchronous full information model with a nonadaptive malicious adversary. All past protocols for asynchronous Byzantine agreement had been exponential, and no protocol for asynchronous leader election had been known. Our protocols tolerate up to (1/3 - epsilon) . n faulty processors, for any positive constant E. they are Monte Carlo, succeeding with probability 1 - o(1) for Byzantine agreement, and constant probability for leader election. A key technical contribution of our article is a new approach for emulating Feige's lightest bin protocol, even with adversarial message scheduling.

关键词： Byzantine agreement distributed algorithms asynchronous communication probabilistic method Monte Carlo algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Asynchronous Byzantine Agreement and Leader Election with Full Information

引用

acm TRANSACTIONS ON algorithms 2010年第4期6卷 1–28页

关键词： Byzantine agreement distributed algorithms asynchronous communication probabilistic method Monte Carlo algorithms

来源：评论

学校读者我要写书评

暂无评论

One-Counter Markov Decision Processes

One-Counter Markov Decision Processes

引用

21st annual acm/siam symposium on discrete algorithms

作者： Brazdil, T. Brozek, V. Etessami, K. Kucera, A. Wojtczak, D. Masaryk Univ Fac Informat CS-60177 Brno Czech Republic Univ Edinburgh Sch Informat Edinburgh EH8 9YL Midlothian Scotland CWI Amsterdam Netherlands

ISBN: (纸本)9780898717013

We study the computational complexity of some central analysis problems for One-Counter Markov Decision Processes (OC-MDPs), a class of finitely-presented, countable-state MDPs. OC-MDPs extend finite-state MDPs with an unbounded counter. the counter can be incremented, decremented, or not changed during each state transition, and transitions may be enabled or not depending on both the current state and on whether the counter value is 0 or not. Some states are "random", from where the next transition is chosen according to a given probability distribution, while other states are "controlled", from where the next transition is chosen by the controller. Different objectives for the controller give rise to different computational problems, aimed at computing optimal achievable objective values and optimal strategies. OC-MDPs are in fact equivalent to a controlled extension of (discrete-time) Quasi-Birth-Death processes (QBDs), a purely stochastic model heavily studied in queueing theory and applied probability. they can thus be viewed as a natural "adversarial" extension of a classic stochastic model. they can also be viewed as a natural probabilistic/controlled extension of classic one-counter automata. OC-MDPs also subsume (as a very restricted special case) a recently studied MDP model called "solvency games" that model a risk-averse gambling scenario. Basic computational questions for OC-MDPs include "termination" questions and "limit" questions, such as the following: does the controller have a strategy to ensure that the counter (which may, for example, count the number of jobs in the queue) will hit value 0 (the empty queue) almost surely (as.)? Or that the counter will have lint sup value co, as.? Or, that it will hit value 0 in a selected terminal state, a.s.? Or, in case such properties are not satisfied almost surely, compute their optimal probability over all strategies. We provide new upper and lower bounds on the complexity of such problems. Specifically,

关键词： Stochastic models

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the 20th annual acm-siam symposium on discrete algorithms

Proceedings of the 20th Annual ACM-SIAM Symposium on Discret...

引用

20th annual acm-siam symposium on discrete algorithms

ISBN: (纸本)9780898716801

the proceedings contain 135 papers. the topics discussed include: improved bounds and new techniques for Daveport-Schinzel sequences and their generalizations;perfect matchings via uniform sampling in regular bipartite graphs;the ratio index for budgeted learning, with applications;approximation algorithms for restless bandit problems;better algorithms for benign bandits;comparison-based time-space lower bounds for selection;linear-time algorithms for geometric graphs with sublinearly many crossings;self-overlapping curves revisited;line transversals of convex polyhedra in R3;optimal halfspace range reporting in three dimensions;decomposition of multiple coverings into more parts;on stars and steiner stars. II;and combinatorial algorithms for nearest neighbors, near-duplicates and small-world design.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts

Loopless Generation of Multiset Permutations using a Constan...

引用

20th annual acm-siam symposium on discrete algorithms

作者： Williams, Aaron Univ Victoria Dept Comp Sci Victoria BC V8W 3N4 Canada

ISBN: (纸本)9780898716801

this paper answers the following mathematical question: Can multiset permutations be ordered so that each permutation is a prefix shift of the previous permutation? Previously, the answer was known for the permutations of any set, and the permutations of any multiset whose corresponding set contains only two elements. this paper also answers the following algorithmic question: Can multiset permutations be generated by a loopless algorithm that uses sublinear additional storage? Previously, the best loopless algorithm used a linear amount of additional storage. the answers to these questions are both yes.

关键词：

来源：评论

学校读者我要写书评

暂无评论

An Efficient Sparse Regularity Concept

An Efficient Sparse Regularity Concept

引用

20th annual acm-siam symposium on discrete algorithms

作者： Coja-Oghlan, Amin Cooper, Colin Frieze, Alan Univ Edinburgh Sch Informat Edinburgh EH8 9YL Midlothian Scotland Univ London Kings Coll London Dept Comp Sci London WC2R 2LS England Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA

ISBN: (纸本)9780898716801

Let A be a 0/1 matrix of size m x n, and let p be the density of A (i.e., the number of ones divided by m . n). We show that A can be approximated in the cut norm within epsilon . mnp by a sum of cut matrices (of rank 1), where the number of summands is independent of the size m . n of A, provided that A satisfies a certain boundedness condition. the decomposition can be computed in polynomial time. this result extends the work of Frieze and Kannan (Combinatorica 1999) to sparse matrices. As an application, we obtain efficient 1 - epsilon approximation algorithms for "bounded" instances of MAX CSP problems.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Appointment Scheduling with discrete Random Durations

Appointment Scheduling with Discrete Random Durations

引用

20th annual acm-siam symposium on discrete algorithms

作者： Begen, Mehmet A. Queyranne, Maurice Univ British Columbia Sander Sch Business Vancouver BC V6T 1Z2 Canada

ISBN: (纸本)9780898716801

We consider the problem of determining optimal appointment schedule for a given sequence of jobs (e.g., medical procedures) on a single processor (e.g., operating room, examination facility), to minimize the expected total underage and overage costs when each job has a random processing duration given by a joint discrete probability distribution. Simple conditions on the cost rates imply that the objective function is submodular and L-convex. then there exists an optimal appointment schedule which is integer and can be found in polynomial time. Our model can handle a given due date for the total processing (e.g., end of day for an operating room) after which overtime is incurred and, no-shows and emergencies.

关键词： Operating rooms

来源：评论

学校读者我要写书评

暂无评论

From coding theory to efficient pattern matching

From coding theory to efficient pattern matching

引用

20th annual acm-siam symposium on discrete algorithms

作者： Clifford, Raphael Efremenko, Klim Porat, Ely Rothschild, Amir Univ Bristol Dept Comp Sci Bristol BS8 1UB Avon England Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Weizmann Inst Sci IL-76100 Rehovot Israel

ISBN: (纸本)9780898716801

We consider the classic problem of pattern matching with few mismatches in the presence of promiscuously matching wildcard symbols. Given a text t of length it and a pattern p of length m with optional wildcard symbols and a bound k, our algorithm finds all the alignments for which the pattern matches the text with Hamming distance at most k and also returns the location and identity of each mismatch. the algorithm we present is deterministic and runs in (O) over tilde (kn) time, matching the best known randomised time complexity to within logarithmic factors. the solutions we develop borrow from the tool set of algebraic coding theory and provide a new framework in which to tackle approximate pattern matching problems.

关键词： Pattern matching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：