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

32nd IEEE INFOCOM Conference

作者： Wu, Lidong Du, Hongwei Wu, Weili Li, Deying Lv, Jing Lee, Wonjun Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA Harbin Inst Technol Shenzhen Grad Sch Shenzhen Peoples R China Shenzhen Key Lab Internet Informat Collaborat Shenzhen Peoples R China Renmin Univ China Sch Informat Beijing 100872 Peoples R China Korea Univ Dept Comp Sci & Engn Seoul South Korea

ISBN: (纸本)9781467359467

Given a requested area, the Minimum Connected Sensor Cover problem is to find a minimum number of sensors such that their communication ranges induce a connected graph and their sensing ranges cover the requested area. Several polynomial-time approximation algorithms have been designed previously in the literature. Their best known performance ratio is O(r ln n) where r is the link radius of the sensor network and n is the number of sensors. In this paper, we will present two polynomial-time approximation algorithms. The first one is a random algorithm, with probability 1 - epsilon, producing an approximation solution with performance ratio O(log(3) n log log n), independent from r. The second one is a deterministic approximation with performance ratio O(r), independent from n.

关键词： approximation theory computational complexity deterministic algorithms graph theory wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

New Results on the Online Pricing Problem

New Results on the Online Pricing Problem

引用

24th International Symposium on algorithms and Computation

作者： Xiang, Xiangzhong Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9783642450303

We study the online pricing problem where there are m identical items on sale and a sequence of users u(1), u(2),... arrive one by one. Each u(i) has a non-increasing acceptable price function phi(i)(center dot) where phi(i)(x) is the highest unit price u(i) is willing to pay for x items. Upon the arrival of a user, the seller needs to decide the number of items to be sold to the user and at what price. The goal is to maximize the revenue of the seller, which is the sum of money paid by all users. For the case when the items are divisible and can be sold fractionally, we improve the results of Zhang et al. [19]. We design a new deterministic algorithm Dp-DIV and prove that it has competitive ratio O(Pi(log*)(j=1) (h-1) log((j)) h) where h is the highest unit price a user is willing to pay;our algorithm is substantially better than the O(h(3) (log2-1/2h)) - competitive algorithm of Zhang et al. We also prove that no randomized algorithm can do better than Omega(log h)-competitive. For the case when items are indivisible, there is no known result. We show in this paper that any deterministic algorithm for this case must have competitive ratio at least Omega(h)-competitive. Then, we give the first competitive randomized algorithm Rp-INDIV with competitive ratio O(Pi(log* h-1)(j=1)log((j)) h). If h is known ahead of time, we can reduce the competitive ratio to O(log h). Besides, we prove that no randomized algorithm can do better than Omega(log h)-competitive.

关键词： New Results Online Pricing identical items randomized algorithms deterministic algorithms Consumers Indivisible Pricing Divisible REVENUE Sales Money Remuneration Wages

来源：评论

学校读者我要写书评

暂无评论

Approximate Lazy Evaluation of Influence Diagrams

Approximate Lazy Evaluation of Influence Diagrams

引用

15th Conference of the Spanish-Association-for-Artificial-Intelligence (CAEPIA)

作者： Cabanas, Rafael Cano, Andres Gomez-Olmedo, Manuel Madsen, Anders L. Univ Granada CITIC Dept Comp Sci & Artificial Intelligence E-18071 Granada Spain HUGIN EXPERT Aalborg Denmark Aalborg Univ Dept Comp Sci Aalborg Denmark

ISBN: (纸本)9783642406423;9783642406430

Influence Diagrams are a tool used to represent and solve decision problems under uncertainty. One of the most efficient exact methods used to evaluate Influence Diagrams is Lazy Evaluation. This paper proposes the use of trees for representing potentials involved in an Influence Diagram in order to obtain an approximate Lazy Evaluation of decision problems. This method will allow to evaluate complex decision problems that are not evaluable with exact methods due to their computational cost. The experimental work compares the efficiency and goodness of the approximate solutions obtained using different kind of trees.

关键词： Influence Diagram Approximate computation Lazy Evaluation deterministic algorithms Context-specific independencies

来源：评论

学校读者我要写书评

暂无评论

Separations in Query Complexity Based on Pointer Functions 16

Separations in Query Complexity Based on Pointer Functions

引用

48th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Ambainis, Andris Balodis, Kaspars Belovs, Aleksandrs Lee, Troy Santha, Miklos Smotrovs, Juris Univ Latvia Fac Comp Riga Latvia Univ Latvia IMCS Riga Latvia CWI Amsterdam Netherlands Nanyang Technol Univ SPMS Singapore Singapore NUS CQT Singapore Singapore NUS MajuLab Singapore Singapore CNRS IRIF Paris France

ISBN: (纸本)9781450341325

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function f on n = 2(k) bits defined by a complete binary tree of NAND gates of depth k, which achieves R-0(f) = O(D(f)(0.7537...)). We show this is false by giving an example of a total boolean function f on n bits whose deterministic query complexity is Omega(n/log(n)) while its zero-error randomized query complexity is (O) over tilde(root n). We further show that the quantum query complexity of the same function is (O) over tilde (n(1/4)), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total boolean function g on n variables that has zero-error randomized query complexity Omega(n/log(n)) and bounded-error randomized query complexity R(g) = (O) over tilde(root n). This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is Q(E)(g) = (O) over tilde(root n). These functions show that the relations D(f) = O(R-1(f)(2)) and R-0(f) = (O) over tilde (R(f)(2)) are optimal, up to poly-logarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R-0, a 3/2-power separation between Q(E) and R, and a 4th power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by Goos, Pitassi, and Watson which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.

关键词： deterministic algorithms Randomized algorithms Quantum algorithms Monte Carlo Las Vegas

来源：评论

学校读者我要写书评

暂无评论

Feature selection in deterministic policy gradient

引用

JOURNAL OF ENGINEERING-JOE 2020年第13期2020卷 403-406页

作者： Li, Luntong Li, Dazi Song, Tianheng Beijing Univ Chem Technol Inst Automat Beijing 100029 Peoples R China

The authors consider the task of learning control problem in reinforcement learning (RL) with continuous action space. Policy gradient, and in particular the determinist policy gradient (DPG) algorithm, provides a method for solving learning control problem with continuous action space. However, when the RL task is complex enough so that tuning of the function approximation is necessary, hand-tuning for the features is infeasible. In order to solve this problem, the authors extend DPG algorithm by adding an approximate-linear-dependency-based sparsification procedure, which makes DPG algorithm to automatically select the useful and sparse features. As far as the authors know, this is the first time to consider the feature selection problem in DPG. Simulation results illustrate that (i) the proposed algorithm can find the optimal solution of the continuous version of mountain car problem;(ii) the proposed algorithm achieves good performance over a large range of the approximate linear dependency threshold parameter settings.

关键词： learning (artificial intelligence) function approximation learning systems feature selection deterministic algorithms continuous action space learning control problem RL task function approximation hand-tuning DPG algorithm approximate-linear-dependency-based sparsification procedure useful features sparse features feature selection problem mountain car problem approximate linear dependency threshold parameter settings deterministic policy gradient reinforcement learning determinist policy gradient algorithm

来源：评论

学校读者我要写书评

暂无评论

Evolution with size in a locally periodic system: scattering and deterministic maps

引用

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL 2013年第23期46卷 235101-235101页

作者： Dominguez-Rocha, V. Martinez-Mares, M. Univ Autonoma Metropolitana Iztapalapa Dept Fis Mexico City 09340 DF Mexico

In this paper, we study the evolution of the wavefunction with the system size in a locally periodic structure. In particular, we analyse the dependence of the wavefunction with the number of unit cells, which also reflects information about its spatial behaviour in the system. We reduce the problem to a nonlinear map and find an equivalence of its energy regions of single periodicity and weak chaos, with the forbidden and allowed bands of the fully periodic system, respectively. At finite size the wavefunction decays exponentially with the system size, as well as in space, when the energy lies inside a region of single periodicity, while for energies in the weak chaotic region it never decays. At the transition between those regions the wavefunction still decays but in a q-exponential form;we find that the decay length is a half of the mean free path, which is larger than the lattice constant.

关键词： SCATTERING (Mathematics) deterministic algorithms UNIT cell LATTICE constants CYCLES

来源：评论

学校读者我要写书评

暂无评论

Two-Source Extractors for Leaky Sources

Two-Source Extractors for Leaky Sources

引用

IEEE Information Theory Workshop (ITW)

作者： Yu, Yu Li, Xiangxue Qian, Haifeng East China Normal Univ Dept Comp Sci & Technol Shanghai 200062 Peoples R China Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China

ISBN: (纸本)9781467302234;9781467302241

A (worst-case) 2-source extractor is a deterministic algorithm that transforms pairwise independent weak random sources into almost uniform random strings. Despite non-constructive proofs that such objects exist with almost optimal parameters, it has been a longstanding open problem to construct 'explicit' (aka efficient) functions for sources of 'small' constant entropy rate. In particular, best known constructions either require entropy rate of at least 0.4999 (due to Bourgain), or one source must remain with constant entropy rate above half (due to Raz). Motivated by cryptographic applications, we observe that if one source is a leaky source (or it contains a few deterministically extractable entropy), then we will be able to efficiently extract almost all entropy from both sources with nearly optimal entropy loss. Further, our extractor (for leaky sources) does not suffer from the half entropy rate barrier, and it works for all linear (and even sub-linear) entropy sources. The extractor is constructed using the technique of alternating extraction by Dziembowski and Pietrzak (FOCS 2007). Finally, we show that the extractor is almost a worse-case extractor (for the same parameters) in the sense that it only fails for a negligible fraction of sources.

关键词： extraction device entropy deterministic algorithms optimal parameter Transform

来源：评论

学校读者我要写书评

暂无评论

Generation of Diverse Paths in 3D Environments

Generation of Diverse Paths in 3D Environments

引用

IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

作者： Quispe, Ana Huaman Kunz, Tobias Stilman, Mike Georgia Inst Technol Ctr Robot & Intelligent Machines Atlanta GA 30332 USA

ISBN: (纸本)9781467363587

In this paper we propose a deterministic algorithm to produce a set of diverse paths between a given start and goal configuration in 3D environments. These diverse paths have the following properties: 1) They are bounded in length and 2) They are non-visibility-deformable into one another. Maintaining multiple path alternatives is important in practical applications such as planning in dynamic environments, in which a path may unexpectedly become infeasible due to unforeseen environmental changes. We present our approach, the distance cost considered ( based on the path deformability concept previously introduced in [11]) and finally show results of simulated experiments that exemplify the effectiveness of our algorithm.

关键词： deterministic algorithms path planning robots

来源：评论

学校读者我要写书评

暂无评论

Peeling Algorithm for Custom Instruction Identification

Peeling Algorithm for Custom Instruction Identification

引用

IEEE Asia Pacific Conference on Circuit and System (APCCAS)

作者： Zhao, Kang Bian, Jinian Tsinghua Univ EDA Lab Dept Comp Sci & Technol Beijing 100084 Peoples R China

ISBN: (纸本)9781424474561

To speedup the custom instruction identification for the application specific instruction-set processor (ASIP), this paper proposes a peeling algorithm. It starts with the maximal valid pattern, and then gets a set of valid sub-patterns through deleting the source and sink respectively. Furthermore, a local priority is proposed for the exhaustive pruning. The final experiment indicates a distinct speedup compared to the fastest deterministic algorithm.

关键词： instruction Customs Customization Speeding deterministic algorithms algorithms Valid

来源：评论

学校读者我要写书评

暂无评论

Optimal Monte Carlo algorithms

Optimal Monte Carlo algorithms

引用

IEEE John Vincent Atanasoff International Symposium on Modern Computing

作者： Dimov, Ivan T. Bulgarian Acad Sci Dept Parallel Algorithms Inst Parallel Proc Sofia 1113 Bulgaria

ISBN: (纸本)0769526438

The question "what Monte Carlo can do and cannot do efficiently " is discussed for some functional spaces that define the regularity of the input data. Important for practical computations data classes are considered: classes of functions with bounded derivatives and Holder type conditions. Theoretical performance analysis of some algorithms with unimprovable rate of convergence is given. Estimates of complexity of two classes of algorithms - deterministic and randomized for the solution of a class of integral equations are presented.

关键词： Monte Carlo algorithms deterministic algorithms integral equations unimprovable rate of convergence

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：