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

On an optimal randomized acceptor for graph nonisomorphism

INFORMATION PROCESSING LETTERS 2012年第5期112卷 166-171页

作者： Hirsch, Edward A. Itsykson, Dmitry Russian Acad Sci Steklov Inst Math St Petersburg St Petersburg 191023 Russia

An acceptor for a language L is an algorithm that accepts every input in L and does not stop on every input not in L. An acceptor Opt for a language L is called optimal if for every acceptor A for this language there exists polynomial p(A) such that for every x is an element of L, the running time time(Opt)(x) of Opt on x is bounded by p(A)(time(A)(x) + vertical bar x vertical bar) for every x is an element of L. (Note that the comparison of the running time is done pointwise, i.e., for every word of the language.) The existence of optimal acceptors is an important open question equivalent to the existence of p-optimal proof systems for many important languages (Krajicek and Pudlak, 1989;Sadowski, 1999;Messner, 1999 [9,13,11]). Yet no nontrivial examples of languages in NP boolean OR co-NP having optimal acceptors are known. In this short note we construct a randomized acceptor for graph nonisomorphism that is optimal up to permutations of the vertices of the input graphs, i.e., its running time on a pair of graphs (G(1). G(2)) is at most polynomially larger than the maximum (in fact, even the median) of the running time of any other acceptor taken over all permuted pairs (pi(1) (G(1)). pi(2) (G(2))). One possible motivation is the (pointwise) optimality in the class of acceptors based on graph invariants where the time needed to compute an invariant does not depend much on the representation of the input pair of nonisomorphic graphs. In fact, our acceptor remains optimal even if the running time is compared to the average-case running time over all permuted pairs. We introduce a natural notion of average-case optimality (not depending on the language of graph nonisomorphism) and show that our acceptor remains average-case optimal for any probability distribution on the inputs that respects permutations of vertices. (C) 2011 Elsevier By. All rights reserved.

关键词： Computational complexity optimal algorithm Graph isomorphism

来源：评论

学校读者我要写书评

暂无评论

optimal semi-online algorithms for scheduling problems with reassignment on two identical machines

引用

INFORMATION PROCESSING LETTERS 2011年第9期111卷 423-428页

作者： Min, Xiao Liu, Jing Wang, Yuqing Jiaxing Univ Coll Math & Informat Engn Jiaxing 314001 Peoples R China

In this paper, we consider semi-online minimum makespan scheduling problem with reassignment on two identical machines. Two versions are discussed. In the first version, one can reassign the last job of one machine that is based on the problem proposed by Tan and Yu (2008) 11 in which case the last job of each machine is allowed to be reassigned. An optimal algorithm which has the same competitive ratio root 2 is presented. In the second version we consider the combination of the next two conditions: the total size of all jobs is known in advance and one can reassign the last job of one machine. For this problem an optimal algorithm with competitive ratio is also given. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Scheduling Reassignment Competitive ratio optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

Simple and optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2022年第1期23卷 1-61页

作者： Li, Zhize Li, Jian Carnegie Mellon Univ Dept Elect & Comp Engn Pittsburgh PA 15213 USA Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China

We propose and analyze several stochastic gradient algorithms for finding stationary points or local minimum in nonconvex, possibly with nonsmooth regularizer, finite-sum and online optimization problems. First, we propose a simple proximal stochastic gradient algorithm based on variance reduction called ProxSVRG+. We provide a clean and tight analysis of ProxSVRG+, which shows that it outperforms the deterministic proximal gradient descent (ProxGD) for a wide range of mini -batch sizes, hence solves an open problem proposed in Reddi et al. (2016b). Also, ProxSVRG+ uses much less proximal oracle calls than ProxSVRG (Reddi et al., 2016b) and extends to the on-line setting by avoiding full gradient computations. Then, we further propose an optimal algorithm, called SSRGD, based on SARAH (Nguyen et al., 2017) and show that SSRGD further improves the gradient complexity of ProxSVRG+ and achieves the the optimal upper bound, matching the known lower bound of (Fang et al., 2018;Li et al., 2021). Moreover, we show that both ProxSVRG+ and SSRGD enjoy automatic adaptation with local structure of the objective function such as the Polyak-Lojasiewicz (PL) condition for nonconvex functions in the finite-sum case, i.e., we prove that both of them can automatically switch to faster global linear convergence without any restart performed in prior work ProxSVRG (Reddi et al., 2016b). Finally, we focus on the more challeng-ing problem of finding an (f, 6)-local minimum instead of just finding an epsilon-approximate (first-order) stationary point (which may be some bad unstable saddle points). We show that SSRGD can find an (f, 6)-local minimum by simply adding some random perturbations. Our algorithm is almost as simple as its counterpart for finding stationary points, and achieves similar optimal rates.

关键词： nonconvex optimization optimal algorithm proximal gradient descent variance re-duction local minimum

来源：评论

学校读者我要写书评

暂无评论

optimal conditional estimation: Average case setting

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2001年第3期109卷 649-666页

作者： Kacewicz, B Univ Min & Met Dept Appl Math Krakow Poland

We consider an estimation problem which appears in the identification of systems by means of restricted complexity models: find the optimal approximation to an element of a linear normed space (a system) based on noisy information, subject to the restriction that approximations (models) can be selected from a prescribed subspace;M of the problem element space. In contrast to the worst-case optimization criterion, which may be pessimistic, in this paper the quality of an identification algorithm is measured by its local average performance. Two types of local average errors are considered: for a given information (measurement) y and for a given unknown element x, the latter in two versions. For a wide spectrum of norms in the measurement space, we define an optimal algorithm and give expressions for its average errors which show the dependence on information, information errors, unmodelled dynamics, and norm in the measurement space.

关键词： local average error conditional identification optimal algorithm optimal information

来源：评论

学校读者我要写书评

暂无评论

ON THE optimal LINEAR CONTRACTION ORDER OF TREE TENSOR NETWORKS, AND BEYOND

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2024年第5期46卷 B647-B668页

作者： Stoian, Mihail Milbradt, Richard M. Mendl, Christian B. Tech Univ Munich Sch CIT Dept Comp Sci Boltz Mannstr 3 D-85748 Garching Germany Tech Univ Munich Inst Adv Study Lichtenbergstr 2a D-85748 Garching Germany

The contraction cost of a tensor network depends on the contraction order. However, the optimal contraction ordering problem is known to be NP-hard. We show that the linear contraction ordering problem for tree tensor networks admits a polynomial-time algorithm, by drawing connections to database join ordering. The result relies on the adjacent sequence interchange property of the contraction cost, which enables a global decision of the contraction order based on local comparisons. Based on that, we specify a modified version of the IKKBZ database join ordering algorithm to find the optimal tree tensor network linear contraction order. Finally, we extend our algorithm as a heuristic to general contraction orders and arbitrary tensor network topologies.

关键词： tensor networks contraction ordering database join ordering einsum optimal algorithm dynamic programming

来源：评论

学校读者我要写书评

暂无评论

On generalized optimal scheduling of high data-rate bursts in CDMA systems

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2003年第2期51卷 261-266页

作者： Lau, VKN Kwok, YK Univ Hong Kong Dept Elect & Elect Engn Hong Kong Hong Kong Peoples R China

In a code-division multiple access (CDMA)-based wireless communication system, forward link is power limited and reverse link is interference limited. With power control and statistical multiplexing, voice services can be supported reasonably well. However, for high data-rate services, a more comprehensive scheduling mechanism is needed in order to achieve a high capacity while satisfying the forward and reverse link constraints. In this paper, we formulate the high data-burst scheduling as a integer programming problem using a generic CDMA system model. We also suggest an optimal algorithm for generating scheduling solutions. With cdma2000 system details plugged in the proposed algorithm, it is found that our algorithm considerably outperforms several fast heuristics, including equal sharing, first-come-first-served, longest delay first, and shortest burst first.

关键词： burst scheduling code-division multiple access (CDMA) high data rate (HDR) optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

A Novel Secondary optimal Control for Multiple Battery Energy Storages in a DC Microgrid

引用

IEEE TRANSACTIONS ON SMART GRID 2020年第5期11卷 3716-3725页

作者： Zhou, Jianyu Shi, Mengxuan Chen, Yin Chen, Xia Wen, Jinyu He, Haibo Huazhong Univ Sci & Technol State Key Lab Adv Electromagnet Engn & Technol Wuhan 430074 Peoples R China Huazhong Univ Sci & Technol Sch Elect & Elect Engn Wuhan 430074 Peoples R China Univ Strathclyde Dept Elect & Elect Engn Glasgow G1 1XW Lanark Scotland Univ Rhode Isl Dept Elect Biomed & Comp Engn Kingston RI 02881 USA

The distributed controller consisting of a voltage controller and a power controller is commonly employed on the secondary control layer in the DC microgrid. In this paper, a novel optimal control based on the PI consensus algorithm is proposed for multiple battery energy storages (BESs) in an islanded DC microgrid. Compared with the conventional distributed voltage controller, the proposed scheme improves the system robustness to time delays. The steady-state analysis is conducted to verify that the proposed scheme can take effect in case of time delays. The impact of the secondary controller on the dynamics of the system under time delays is investigated by the eigenvalue analysis. Simulation results confirm that favorable power sharing and DC voltage regulation as well as robustness to time delays achieved by optimal control in an islanded microgrid with multiple BESs and constant power load (CPL).

关键词： DC microgrid battery energy storage distributed control optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

optimal Security-Aware Query Processing

引用

PROCEEDINGS OF THE VLDB ENDOWMENT 2014年第12期7卷 1307-1318页

作者： Guarnieri, Marco Basin, David Swiss Fed Inst Technol Dept Comp Sci Inst Informat Secur Zurich Switzerland

Security-Aware Query Processing is the problem of computing answers to queries in the presence of access control policies. We present general impossibility results for the existence of optimal algorithms for Security-Aware Query Processing and classify query languages for which such algorithms exist. In particular, we show that for the relational calculus there are no optimal algorithms, whereas optimal algorithms exist for some of its fragments, such as the existential fragment. We also establish relationships between two different models of Fine-Grained Access Control, called Truman and Non Truman models, which have been previously presented in the literature as distinct. For optimal Security-Aware Query Processing, we show that the Non-Truman model is a special case of the Truman model for boolean queries in the relational calculus, moreover the two models coincide for more powerful languages, such as the relational calculus with aggregation operators. In contrast, these two models are distinct for non-boolean queries.

关键词： Query languages Access control Calculations Mathematical operators Query processing Access control policies Aggregation operator Boolean queries Impossibility results optimal algorithm optimal security Relational calculus Security aware

来源：评论

学校读者我要写书评

暂无评论

Study on the method of colour image noise reduction based on optimal channel-processing

引用

IET IMAGE PROCESSING 2018年第9期12卷 1545-1549页

作者： Wang, Yutan Dai, Yingpeng Liu, Xiangnan Liu, Bohan Guo, Xiaoyun Ningxia Univ Sch Mech Engn Yinchuan Peoples R China

The methods of the image noise reduction based on optimal channel-processing to enhance image quality are studied. According to different noise with the different ratio in colour components, different noise reduction technologies are used for noise reduction. Then the optimal algorithm is automatically selected as the ultimate way of noise reduction in each channel. For the purpose of optimal noise reduction effect, this study presents a method of combining the quadratic optimisation with the variable window processing. The quadratic optimisation provides a good environment for noise reduction by decreasing complexity of mixed noise and the variable window processing calibrates the image smoothing result. Compared with mean filtering, median filtering and adaptive filtering, the image quality processed by the proposed algorithm is generally improved by >2 dB.

关键词： image enhancement image denoising image colour analysis adaptive filters optimisation median filters filtering theory wavelet transforms colour image noise reduction optimal channel-processing image quality different noise reduction technologies optimal algorithm optimal noise reduction effect quadratic optimisation variable window processing mixed noise image smoothing result noise figure 2 0 dB

来源：评论

学校读者我要写书评

暂无评论

optimal PARALLEL MERGING AND SORTING WITHOUT MEMORY CONFLICTS

引用

IEEE TRANSACTIONS ON COMPUTERS 1987年第11期36卷 1367-1369页

作者： AKL, SG SANTORO, N CARLETON UNIV SCH COMP SCIDISTRIBUTED COMP GRPOTTAWA K1S 5B6ONTARIOCANADA

A parallel algorithm is described for merging two sorted vectors of total length N. The algorithm runs on a shared-memory model of parallel computation that disallows more than one processor to simultaneously read from or write into the same memory location. It uses k processors where l Â¿ k Â¿ N and requires O(N/k + log k Ã? log N) time. The proposed approach for merging leads to a parallel sorting algorithm that sorts a vector of length N in O(log2 k + N/k) log N) time. Because they modify their behavior and hence their running time according to the number of available processors, the two new algorithms are said to be self-reconfiguring. In addition, both algorithms are optimal, for k Â¿ N/log2 N, in view of the Â¿(N) and Â¿(N log N) lower bounds on merging and sorting, respectively.

关键词： Memory conflicts merging optimal algorithm parallel computation selection self-reconfiguring algorithm shared-memory module sorting

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：