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

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Li, Ray Stanford Univ Stanford CA 94305 USA

ISBN: (纸本)9781450380539

We prove several tight results on the fine-grained complexity of approximating the diameter of a graph. First, we prove that, for any l > 0, assuming the Strong Exponential Time Hypothesis (SETH), there are no near-linear time 2 - epsilon-approximation algorithms for the Diameter of a sparse directed graph, even in unweighted graphs. This result shows that a simple near-linear time 2-approximation algorithm for Diameter is optimal under SETH, answering a question from a survey of Rubinstein and Vassilevska-Williams (SIGACT '19) for the case of directed graphs. In the same survey, Rubinstein and Vassilevska-Williams also asked if it is possible to show that there are no 2 - epsilon approximation algorithms for Diameter in a directed graph in O(n(1.499)) time. We show that, assuming a hypothesis called NSETH, one cannot use a deterministic SETH-based reduction to rule out the existence of such algorithms. Extending the techniques in these two results, we characterize whether a 2 - epsilon approximation algorithm running in time O(n(1+delta)) for the Diameter of a sparse directed unweighted graph can be ruled out by a deterministic SETH-based reduction for every delta is an element of (0, 1) and essentially every epsilon is an element of (0, 1), assuming NSETH. This settles the SETH-hardness of approximating the diameter of sparse directed unweighted graphs for deterministic reductions, up to NSETH. We make the same characterization for randomized SETH-based reductions, assuming another hypothesis called NUNSETH. We prove additional hardness and non-reducibility results for undirected graphs.

关键词： Graph Diameter Strong Exponential Time Hypothesis nondeterministic algorithm Fine-Grained Complexity Hopset

来源：评论

学校读者我要写书评

暂无评论

Effective nondeterministic positive definiteness test for unidiagonal integral matrices 18

Effective nondeterministic positive definiteness test for un...

引用

18th International Symposium on Symbolic and Numeric algorithms for Scientific Computing (SYNASC)

作者： Mroz, Andrzej Nicolaus Copernicus Univ Fac Math & Comp Sci Ul Chopina 12-18 PL-87100 Torun Poland

ISBN: (纸本)9781509057078

For standard algorithms verifying positive definiteness of a matrix A is an element of M-n(R) based on Sylvester's criterion, the computationally pessimistic case is this when A is positive definite. We present an algorithm realizing the same task for A is an element of M-n(Z), for which the case when A is positive definite is the optimistic one. The algorithm relies on performing certain edge transformations, called inflations, on the signed graph (bigraph) Delta = Delta(A) associated with A. We provide few variants of the algorithm, including Las Vegas type randomized ones (with precisely described maximal number of steps). The algorithms work very well in practice, in many cases with a better speed than the standard tests. On the other hand, our results provide an interesting example of an application of symbolic computing methods originally developed for different purposes, with a big potential for further generalizations in matrix problems.

关键词： bigraph nondeterministic algorithm positive definite matrix signed graph

来源：评论

学校读者我要写书评

暂无评论

Automated cleaning of point clouds for highway retaining wall condition assessment

Automated cleaning of point clouds for highway retaining wal...

引用

2014 International Conference on Computing in Civil and Building Engineering

作者： Oskouie, Pedram Becerik-Gerber, Burcin Soibelman, Lucio Sonny Astani Department of Civil and Environmental Engineering University of Southern California Los AngelesCA United States

ISBN: (纸本)9780784413616

Continuous condition monitoring and inspection of under-construction highway retaining walls is essential to ensure that construction performance criteria are met. The use of LIDAR systems by the construction industry has been significantly increased in recent years, especially for recording the as-built and as-is conditions of facilities. The high-precision, dense 3-D point clouds generated by 3-D laser scanners can facilitate the process of Asset Condition Assessment (ACA). ACA involves preprocessing the point cloud data, for which point clouds have to be cleaned of any unwanted or occluding objects and noises. As part of this research, the retaining wall point cloud data from an ongoing highway construction project was processed and analyzed. The project uses 3-D laser scanners for regular monitoring of mechanically stabilized earth walls that retain the soil supporting the highway alignment. The temporary steel and wooden brackets that hold formworks on top of the walls along with other construction materials are defined as unwanted objects. The authors have used a non-deterministic algorithm to remove the brackets and noises from the point clouds. Various settings of the algorithm have been analyzed using different sets of data. This paper presents the accuracy and performance of the tested algorithm and its evaluation when comparing the results with manually cleaned point clouds. © ASCE 2014.

关键词： Clouds Dataset RETAINING WALLS Noise Construction Materials reinforced earth retaining walls road alignment nondeterministic algorithm Brackets Brackets Condition assessment Construction Industry laser scanners Freeway Highway construction

来源：评论

学校读者我要写书评

暂无评论

Automated B-H curve identification algorithm combining field simulation with optimisation methods and exploiting parallel computation

引用

IET SCIENCE MEASUREMENT & TECHNOLOGY 2012年第5期6卷 369-375页

作者： Di Barba, P. Komeza, K. Juszczak, E. N. Lecointe, J. P. Napieralski, P. Hihat, N. Univ Pavia Dept Elect Engn I-27100 Pavia Italy Tech Univ Lodz Inst Mechatron & Informat Syst PL-90924 Lodz Poland Univ Lille Nord France F-59000 Lille France UA LSEE F-62400 Bethune France Tech Univ Lodz Inst Informat Technol PL-90924 Lodz Poland

The study proposes an automated procedure for linking an identification algorithm implemented in a general-purpose environment (MatLab) with a commercial finite-element code for magnetic field analysis (VF-Opera). The method is used to identify the B-H curves of anisotropic magnetic laminations in the direction normal to the sheet surface with the aid of a multiprocessor computer to benefit from parallel computing. The proposed approach, based on a non-deterministic algorithm, makes it possible to determine the entire B-H curve and is therefore an advancement on the commonly used assumption of constant permeability.

关键词： Optimization methods magnetization curve field simulation nondeterministic algorithm PARALLEL PROCESSING (COMPUTERS) Automation

来源：评论

学校读者我要写书评

暂无评论

Maximizing communication concurrency via link-layer packet salvaging in mobile ad hoc networks

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2007年第4期6卷 449-462页

作者： Yu, Chansu Shin, Kang G. Song, Lubo Cleveland State Univ Dept Elect & Comp Engn Cleveland OH 44115 USA Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

Carrier-sense Medium Access Control (MAC) protocols such as the IEEE 802.11 Distributed Coordination Function (DCF) avoid collisions by holding up pending packet transmission requests when a carrier signal is observed above a certain threshold. However, this often results in unnecessarily conservative communication, thus making it difficult to maximize the utilization of the spatial spectral resource. This paper shows that a higher aggregate throughput can be achieved by allowing more concurrent communications and adjusting the communication distance on the fly, which needs provisions for the following two areas: On the one hand, carrier sense-based MAC protocols do not allow aggressive communication attempts when they are within the carrier senseable area. On the other hand, the communication distance is generally neither short nor adjustable because multihop routing protocols strive for providing minimum hop paths. This paper proposes a new MAC algorithm, called Multiple Access with Salvation Army (MASA), which adopts less sensitive carrier sensing to promote more concurrent communications and adjusts the communication distance adaptively via "packet salvaging" at the MAC layer. Extensive simulation based on the ns-2 has shown MASA to outperform the DCF, particularly in terms of packet delay. We also discuss the implementation of MASA based on the DCF specification.

关键词： mobile ad hoc networks carrier sense medium access control capture effect nondeterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

MINIMIZATION OF AND EXOR EXPRESSIONS USING REWRITE RULES

引用

IEEE TRANSACTIONS ON COMPUTERS 1993年第5期42卷 568-576页

作者： BRAND, D SASAO, T KYUSHU INST TECHNOL DEPT COMP SCI & ELECTR ENGN IIZUKA 820 JAPAN

This paper considers conditions for generating optimal two-level AND-EXOR representations using rewrite rules. Four results are presented. First, a necessary condition for obtaining minimality is a temporary increase in the size of expressions during minimization. Second, a sufficient condition for obtaining minimality consists of adding certain two rules to rule sets proposed in the literature. Third, we define transformations that allow the minimization of an expression to proceed by minimizing a transformed expression instead. Fourth, we determine experimentally that the above three theoretical results lead to better benchmarks results as well.

关键词： EXOR L-TRANSFORMATION LOGIC MINIMIZATION nondeterministic algorithm REED-MULLER EXPANSION 2-LEVEL REPRESENTATION

来源：评论

学校读者我要写书评

暂无评论

HIERARCHIES OF RECURSIVE COMPUTATIONS

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1979年第4期7卷 271-286页

作者： STIMSON, MJ SAVITCH, WJ UNIV CALIF SAN DIEGO DEPT APPL PHYS & INFORMAT SCIPROGRAM COMP SCILA JOLLACA 92093

A recursive version of the Turing machine model is used to analyze the time and storage complexity of recursive algorithms. Hierarchy theorems are proven for time and for width of recursion (the amount of storage used at a level). A particular language is shown to be the “hardest” language to recognize without recursion. Previous results relating recursive and non-recursive time bounded computations are sharpened.

关键词： Turing machine Tape complexity Time complexity Recursive algorithms nondeterministic algorithm Hierarchy 5.25 5.26 5.23

来源：评论

学校读者我要写书评

暂无评论

GEDANKEN - A SIMPLE TYPELESS LANGUAGE BASED ON PRINCIPLE OF COMPLETENESS AND REFERENCE CONCEPT

引用

COMMUNICATIONS OF THE ACM 1970年第5期13卷 308-&页

作者： REYNOLDS, JC Argonne National Lab Argonne IL

GEDAN KEN is an experimental programming language with the following characteristics. (1) Any value which is permitted in some context of the language is permissible in any other meaningful context. In particular, functions and labels are permissible results of functions and values of variables. (2) Assignment and indirect addressing are formalized by introducing values, called references, which in turn possess other values. The assignment operation always affects the relation between some reference and its value. (3) All compound data structures are treated as functions. (4) Type declarations are not permitted. The functional approach to data structures and the use of references insure that any process which accepts some data structure will accept any logically equivalent structure, regards less of its internal representation. More generally, any data structure may be implicit; i.e. it may be specified by giving an arbitrary algorithm for computing or accessing its components. The existence of label variables permits the construction of co-routines, quasi-parallel processes, and other unorthodox control mechanisms. A variety of programming examples illustrates the generality of the language. Limitations and possible extensions are discussed briefly. [ABSTRACT FROM AUTHOR]

关键词： applicative language assignment coroutine data structure lambda calculus list processing nondeterministic algorithm programming language quasi-parallel process reference typeless language

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：