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

A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection

THEORETICAL COMPUTER SCIENCE 2015年 602卷 149-157页

作者： Chang, Ching-Lueh Yuan Ze Univ Dept Comp Sci & Engn Taoyuan Taiwan Yuan Ze Univ Innovat Ctr Big Data & Digital Convergence Taoyuan Taiwan

We give a deterministic O (hn(1+1/h))-time (2h)-approximation nonadaptive algorithm for 1-median selection in n-point metric spaces, where h is an element of Z(+) \ {1} is arbitrary. Our proof generalizes that of Chan... 详细信息

关键词： 1-Median selection sublinear-time algorithm Metric space k-Median selection Closeness centrality

来源：评论

学校读者我要写书评

暂无评论

On Random Perfect Matchings in Metric Spaces with Not-too-large Diameters

引用

THEORY OF COMPUTING SYSTEMS 2022年第4期66卷 847-860页

作者： Chang, Ching-Lueh Yuan Ze Univ Dept Comp Sci & Engn Taoyuan Taiwan

Let ([n], d) be a metric space with diameter Delta and with average distance (r) over bar, where [n] = {1, 2, ..., n}. We show that if Delta = o(n (r) over bar), then Sigma(left perpendicularn/2right perpendicular)(i=1) d(pi(2i - 1), pi(2i)) is (1/2 +/- o(1))n (r) over bar with probability 1 - omicron(1) over a uniformly random permutation pi : [n] -> [n]. In particular, a uniformly random perfect matching in ([n], d) has size concentrating around n (r) over bar /2 when n is even and Delta = o(n (r) over bar). Our result has implications for finding maximum travelling salesman tours in metric spaces.

关键词： Metric space Random matching Concentration bound sublinear-time algorithm Travelling salesman problem

来源：评论

学校读者我要写书评

暂无评论

Fast Neighborhood Rendezvous

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2022年第3期E105D卷 597-610页

作者： Eguchi, Ryota Kitamura, Naoki Izumi, Taisuke Nagoya Inst Technol Nagoya Aichi 4668555 Japan Osaka Univ Suita Osaka 5650871 Japan

In the rendezvous problem, two computing entities (called agents) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous neighborhood rendezvous problem, where the agents are initially located at two adjacent vertices. While this problem can be trivially solved in O(Delta) rounds (Delta is the maximum degree of the graph), it is highly challenging to reveal whether that problem can be solved in o(Delta) rounds, even assuming the rich computational capability of agents. The only known result is that the time complexity of O(root n) rounds is achievable if the graph is complete and agents are probabilistic, asymmetric, and can use whiteboards placed at vertices. Our main contribution is to clarify the situation (with respect to computational models and graph classes) admitting such a sublinear-time rendezvous algorithm. More precisely, we present two algorithms achieving fast rendezvous additionally assuming bounded minimum degree, unique vertex identifier, accessibility to neighborhood IDs, and randomization. The first algorithm runs within (O) over tilde( root n Delta/delta + n/delta) rounds for graphs of the minimum degree larger than root n, where n is the number of vertices in the graph, and delta is the minimum degree of the graph. The second algorithm assumes that the largest vertex ID is O(n), and achieves (O) over tilde (n/root delta)-round time complexity without using whiteboards. These algorithms attain o(Delta)-round complexity in the case of delta = omega(root n log n) and delta = omega(n(2/3) log(4/3) n) respectively. We also prove that four unconventional assumptions of our algorithm, bounded minimum degree, accessibility to neighborhood IDs, initial distance one, and randomization are all inherently necessary for attaining fast rendezvous. That is, one can obtain the Omega(n)-round lower bound if either one of them is removed.

关键词： rendezvous randomized algorithm sublinear-time algorithm whiteboards

来源：评论

学校读者我要写书评

暂无评论

Fast Neighborhood Rendezvous 40

Fast Neighborhood Rendezvous

引用

40th IEEE International Conference on Distributed Computing Systems (ICDCS)

作者： Eguchi, Ryota Kitamura, Naoki Izumi, Taisuke Nagoya Inst Technol Dept Comp Sci Nagoya Aichi Japan

ISBN: (纸本)9781728170022

In the rendezvous problem, two computing entities (called agents) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous neighborhood rendezvous problem, where the agents are initially located at two adjacent vertices. While this problem can be trivially solved in O(Delta) rounds (Delta is the maximum degree of the graph), it is highly challenging to reveal whether that problem can be solved in o(Delta) rounds, even assuming the rich computational capability of agents. The only known result is that the time complexity of O(root n) rounds is achievable if the graph is complete and agents are probabilistic, asymmetric, and can use whiteboards placed at vertices. Our main contribution is to clarify the situation (with respect to computational models and graph classes) admitting such a sublinear-time rendezvous algorithm. More precisely, we present two algorithms achieving fast rendezvous additionally assuming bounded minimum degree, unique vertex identifier, and accessibility to neighborhood IDs. The first algorithm runs within (O) over tilde(root n Delta/delta + n/delta) rounds for graphs of the minimum degree larger than root n, where n is the number of vertices in the graph, and delta is the minimum degree of the graph. The second algorithm assumes that the largest vertex ID is O(n), and achieves (O) over tilde (n/root delta)-round time complexity without using whiteboards. These algorithms attain o(Delta)-round complexity in the case of delta = omega(root nlogn) and delta = omega(n(2/3) log(4/3) n) respectively. We also prove that three unconventional assumptions of our algorithm, bounded minimum degree, accessibility to neighborhood IDs, and initial distance one, are all inherently necessary for attaining fast rendezvous. That is, one can obtain the Omega(n)-round lower bound if either one of them is removed.

关键词： rendezvous randomized algorithm sublinear-time algorithm whiteboards

来源：评论

学校读者我要写书评

暂无评论

On Las Vegas approximations for metric 1-median selection

引用

INFORMATION PROCESSING LETTERS 2019年 146卷 44-48页

作者： Chang, Ching-Lueh Yuan Ze Univ Dept Comp Sci & Engn Taoyuan Taiwan

Consider the problem of finding a point in a metric space ({1, 2, ... , n}, d) with the minimum sum of distances to all points. We show that this problem has a randomized algorithm that (1) always outputs a (2+epsilon)-approximate solution in expected O (n/epsilon(2)) time and that (2) inherits Indyk's [8,9] algorithm to output a (1 + epsilon)-approximate solution in O (n/epsilon(2)) time with probability Omega(1), where epsilon epsilon (0,1). As a by-product, the average distance in ({1, 2, ..., n}, d) can be approximated in O (n/epsilon) time to within a multiplicative factor in [1/2 - epsilon, 1] with probability 1/2 + Omega(1), where epsilon > 0. (C) 2019 Elsevier B.V. All rights reserved.

关键词： 1-median sublinear-time algorithm Metric space Closeness centrality Randomized aigorithms

来源：评论

学校读者我要写书评

暂无评论

A lower bound for metric 1-median selection

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 84卷 44-51页

作者： Chang, Ching-Lueh Yuan Ze Univ Dept Comp Sci & Engn Taoyuan Taiwan

Consider the problem of finding a point in an n-point metric space with the minimum average distance to all points. We show that this problem has no deterministic o(n(2))-query (4-is an element of)-approximation algor... 详细信息

关键词： 1-Median selection Metric space sublinear-time algorithm sublinear-query algorithm Query complexity

来源：评论

学校读者我要写书评

暂无评论

UNATENESS TESTING

UNATENESS TESTING

引用

作者： Baleshzar, Roksana PennState University Libraries

学位级别：Master of Science

We study the problem of testing unateness of functions f:[n]^d -> R. A function f is unate if for every coordinate i in [d], the function is either nonincreasing in the i-th coordinate or nondecreasing in the i-th coordinate. A unateness tester is a randomized algorithm which, given parameter epsilon in (0,1) and oracle access to the input function f, accepts f with probability at least 2/3 if it is unate, and rejects f with probability at least 2/3 if it is epsilon-far from being unate. A unateness tester is adaptive if its queries depend on the answers to its previous queries. Otherwise, it is *** solve the unateness testing problem completely for functions f:[n]^d -> R by giving an optimal O(d (log d + log n)) query nonadaptive tester and a O(d log n) query adaptive tester. We also prove that adaptivity helps for testing unateness of real-valued functions, whereas it does not help for a large class of similar properties including monotonicity.

关键词： sublinear-time algorithm property testing unateness monotonicity

来源：评论

学校读者我要写书评

暂无评论

Deterministic sublinear-time approximations for metric 1-median selection

引用

INFORMATION PROCESSING LETTERS 2013年第8期113卷 288-292页

作者： Chang, Ching-Lueh Yuan Ze Univ Dept Comp Sci & Engn Tao Yuan Taiwan

Given oracle access to an n-point metric space (M, d), let METRIC 1-MEDIAN be the problem of finding argmin(x is an element of M) Sigma(y is an element of M) d(x, y), breaking ties arbitrarily. We show that METRIC 1-MEDIAN has a deterministic nonadaptive O(n(3/2))-time 4-approximation algorithm. (c) 2013 Elsevier B.V. All rights reserved.

关键词： algorithm Metric 1-median selection Median selection sublinear-time algorithm Nonevasive algorithm Query complexity Metric space

来源：评论

学校读者我要写书评

暂无评论

Exposure-resilient extractors and the derandomization of probabilistic sublinear time

引用

COMPUTATIONAL COMPLEXITY 2008年第2期17卷 220-253页

作者： Zimand, Marius Towson Univ Dept Comp & Informat Sci Baltimore MD 21252 USA

There exists a positive constant alpha {0, 1}(m) is a (k, is an element of)-exposure-resilient extractor resistant to q queries if, when the min-entropy of the random variable x is at least k and the random variable ... 详细信息

There exists a positive constant alpha < 1 such that for any function T(n) <= n(alpha) and for any problem L is an element of BPtime(T(n)), there exists a deterministic algorithm running in poly(T(n)) time which decides L, except for at most a 2(-Omega-(T(n) log T(n))) fraction of inputs of length n. The proof uses a novel derandomization technique based on a new type of randomness extractors, called exposure-resilient extractors. An exposure-resilient extractor is an efficient procedure that, from a random variable with imperfect randomness, produces randomness that passes all statistical tests including those that have bounded access to the random variable, with adaptive queries that can depend on the string being tested. More precisely, EXT : {1, 1}(n) x {0, 1}(d) -> {0, 1}(m) is a (k, is an element of)-exposure-resilient extractor resistant to q queries if, when the min-entropy of the random variable x is at least k and the random variable y is uniformly distributed, EXT(x, y) looks E-random to all statistical tests modeled by oracle circuits of unbounded size that can query q bits of x. Besides the extractor that is needed for the proof of the main result (whose parameters are tailored for this application), we construct, for any delta < 1, a polynomial-time computable (k, is an element of)-exposure-resilient extractor with query resistance n(delta), k = n - n(Omega(1)), is an element of = n(-Omega(1)), m = n(-Omega(1)) and d = O(log n).

关键词： sublinear-time algorithm extractor pseudo-random generator

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：