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

INFORMATION PROCESSING LETTERS 2022年 177卷

作者： Bhattacharya, Anup Freund, Yoav Jaiswal, Ragesh Homi Bhabha Natl Inst Sch Comp Sci NISER Bhubaneswar India UCSD CSE La Jolla CA USA IIT Delhi CSE Delhi India

In this work, we study the k-means cost function. Given a dataset X & SUBE;Rd and an integer k, the goal of the Euclidean k-means problem is to find a set of k centers C & SUBE;Rd such that (I)(C, X) & EQUIV;Ex & ISIN;X minc & ISIN;C ?x - c?2 is minimized. Let A(X, k) & EQUIV;minC & SUBE;Rd (D(C, X) denote the cost of the optimal k-means solution. For any dataset X, A(X, k) decreases as k increases. In this work, we try to understand this behavior more precisely. For any dataset X & SUBE;Rd, integer k & GE;1, and a precision parameter epsilon > 0, let L(X, k, epsilon) denote the smallest integer such that A(X, L(X, k, epsilon)) & LE;epsilon middot A(X, k). We show upper and lower bounds on this quantity. Our techniques generalize for the metric k-median problem in metric spaces with bounded doubling dimension. Finally, we observe that for any dataset X, we can compute a set S of size O (L(X, k, epsilon/c)) using D2-sampling such that (I)(S, X) & LE;epsilon middot A(X, k) for some fixed constant c. Some of the applications include new pseudo-approximation guarantees for k means++ and bounds for movement-based coreset constructions.(c) 2022 Elsevier B.V. All rights reserved.

关键词： k-means clustering k-median clustering Coresets randomized algorithms D-2-sampling

来源：评论

学校读者我要写书评

暂无评论

Analysis of consensus sorting via the cycle metric

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第3期44卷 1831-1847页

作者： Avramovic, Ivan Richards, Dana S. George Mason Univ Fairfax VA 22030 USA

Sorting is studied in this paper as an archetypal example to explore the optimizing power of consensus. In conceptualizing the consensus sort, the classical hill-climbing method of optimization is paired with the modern notion that value and fitness can be judged by data mining. Consensus sorting is a randomized sorting algorithm which is based on randomly selecting pairs of elements within an unsorted list (expressed in this paper as a permutation), and deciding whether to swap them based on appeals to a database of other permutations. The permutations in the database are all scored via some adaptive sorting metric, and the decision to swap depends on whether the database consensus suggests a better score as a result of swapping. This uninformed search process does not require the definition of the concept of sorting, but rather depends on selecting a metric which does a good job of distinguishing a good path to the goal, a sorted list. A previous paper has shown that the ability of the algorithm to converge on the goal depends strongly on the metric which is used, and analyzed the performance of the algorithm when number of inversions was used as a metric. This paper continues by analyzing the performance of a much more efficient metric, the number of cycles in the permutation.

关键词： Adaptive sorting randomized algorithms Uninformed search Combinatorics Simulation and modeling

来源：评论

学校读者我要写书评

暂无评论

A constant-time sampling algorithm for binary Gaussian distribution over the integers

引用

INFORMATION PROCESSING LETTERS 2022年 176卷

作者： Du, Yusong Fan, Baoying Wei, Baodian Sun Yat Sen Univ Sch Comp Sci & Engn Guangdong Prov Key Lab Informat Secur Technol Guangzhou 510006 Peoples R China

Discrete Gaussian sampling over the integers is one of fundamental operations in lattice-based cryptography. The binary Gaussian distribution DZ+,(sigma 2) is a special discrete Gaussian distribution with sigma(2) =root 1/(2ln2) and mu = 0 over the set of non-negative integers Z(+), and a sampling algorithm for DZ+,(sigma 2) can be used as the base sampler in a generic algorithm based on rejection sampling for any discrete Gaussian distribution over the integers. We present a constant-time algorithm for sampling from the binary Gaussian distribution DZ+,(sigma 2). It requires no precomputation storage and mainly relies on bitwise operations, which could be more hardware-friendly. Its computational complexity is lower than that of the algorithm based on the full-tree Knuth-Yao method, and its entropy consumption is smaller than that of the full-table access algorithm based on a cumulative distribution table. The Renyi-divergence based security analysis of our constant-time algorithm can also be simplified. (C) 2022 Elsevier B.V. All rights reserved.

关键词： cryptography randomized algorithms discrete Gaussian sampling binary Gaussian distribution timing attack

来源：评论

学校读者我要写书评

暂无评论

The Price of Explainability for Clustering 64

The Price of Explainability for Clustering

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Gupta, Anupam Pittu, Madhusudhan Reddy Svensson, Ola Yuan, Rachel Carnegie Mellon Univ Pittsburgh PA 15213 USA Ecole Polytech Fed Lausanne Lausanne Switzerland

ISBN: (纸本)9798350318944

Given a set of points in d-dimensional space, an explainable clustering is one where the clusters are specified by a tree of axis-aligned threshold cuts. Dasgupta et al. (ICML 2020) posed the question of the price of explainability: the worst-case ratio between the cost of the best explainable clusterings to that of the best clusterings. We show that the price of explainability for k-medians is at most 1 + Hk-1;in fact, we show that the popular Random Thresholds algorithm has exactly this price of explainability, matching the known lower bound constructions. We complement our tight analysis of this particular algorithm by constructing instances where the price of explainability (using any algorithm) is at least (1 - o(1)) ln k, showing that our result is best possible, up to lower-order terms. We also improve the price of explainability for the k-means problem to O(k ln ln k) from the previous O(k ln k), considerably closing the gap to the lower bounds of Omega(k). Finally, we study the algorithmic question of finding the best explainable clustering: We show that explainable k-medians and k-means cannot be approximated better than O(ln k), under standard complexity-theoretic conjectures. This essentially settles the approximability of explainable k-medians and leaves open the intriguing possibility to get significantly better approximation algorithms for k-means than its price of explainability.

关键词： k-means k-medians explainable clustering approximation algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Stochastic MPC Implementation via Policy Learning

引用

IEEE CONTROL SYSTEMS LETTERS 2022年 6卷 3020-3025页

作者： Mammarella, Martina Altamimi, Abdulelah Chamanbaz, Mohammadreza Dabbene, Fabrizio Lagoa, Constantino CNR IEIIT Inst Elect Comp & Telecommun Engn I-10129 Turin Italy Penn State Univ Sch Elect Engn & Comp Sci University Pk PA 16802 USA Univ Sydney Rio Tinto Ctr Mine Automat Australian Ctr Field Robot Sydney NSW 2006 Australia

Stochastic Model Predictive Control (MPC) gained popularity thanks to its capability of overcoming the conservativeness of robust approaches, at the expense of a higher computational demand. This represents a critical issue especially for sampling-based methods. In this letter we propose a policy learning MPC approach, which aims at reducing the cost of solving stochastic optimization problems. The presented scheme relies upon the use of neural networks for identifying a mapping between the current state of the system and the probabilistic constraints. This allows to reduce the sample complexity to be less than or equal to the dimension of the decision variable, significantly scaling down the computational burden of stochastic MPC approaches, while preserving the same probabilistic guarantees. The efficacy of the proposed policy-learning MPC is proved by means of a numerical example.

关键词： Optimization Uncertainty Probabilistic logic Complexity theory Stochastic processes Costs Random variables Constrained control predictive control neural networks randomized algorithms stochastic optimal control

来源：评论

学校读者我要写书评

暂无评论

BALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE

引用

SIAM JOURNAL ON COMPUTING 2022年第6期51卷 1743-1768页

作者： Augustine, John Moses Jr, William K. Redlich, Amanda Upfal, Eli Indian Inst Technol Madras Dept Comp Sci & Engn Chennai 600036 Tamil Nadu India Bowdoin Coll Dept Math Brunswick ME 04011 USA Brown Univ Dept Comp Sci Providence RI 02912 USA

Load balancing is a well-studied problem, with balls-in-bins being the primary frame-work. The greedy algorithm Gresanse\sansedy[d] of Azar et al. [SIAM J. Comput., 29 (1999), pp. 180--200] places each ball by probing d > 1 random bins and placing the ball in the least loaded of them. With high probability, the maximum load under Gresanse\sansedy[d] is exponentially lower than the result when balls are placed uniformly randomly. Vo"\cking [J. ACM, 50 (2003), pp. 568--589] showed that a slightly asymmetric variant, Left[d], provides a further significant improvement. However, this improvement comes at the additional computational cost of imposing structure on the bins. Here, we present a fully decentralized and easy-to-implement algorithm called FirstDiff[d] that combines the simplicity of Gresanse\sansedy[d] and the improved balance of Left[d]. The key idea in FirstDiff[d] is to probe until a different bin size from the first observation is located and then place the ball. Although the number of probes could be quite large for some of the balls, we show that FirstDiff[d] requires only at most d probes on average per ball (in both the standard and the heavily loaded settings). Thus the number of probes is no greater than that of either Gresanse\sansedy[d] or Left[d]. More importantly, we show that FirstDiff[d] closely matches the improved maximum load ensured by Left[d] in both the standard and heavily loaded settings. We further provide a tight lower bound on the maximum load up to O(log log log n) terms. We additionally give experimental data that FirstDiff[d] is indeed as good as Left[d], if not better, in practice.

关键词： load balancing FirstDiff balanced allocation randomized algorithms task alloca-tion

来源：评论

学校读者我要写书评

暂无评论

Data-Driven Abstractions for Robots With Stochastic Dynamics

引用

IEEE TRANSACTIONS ON ROBOTICS 2022年第3期38卷 1686-1702页

作者： Tanner, Herbert G. Stager, Adam Univ Delaware Dept Mech Engn Newark DE 19716 USA

This article describes the construction of stochastic, data-based discrete abstractions for uncertain random processes continuous in time and space. Motivated by the fact that modeling processes often introduce errors which interfere with the implementation of control strategies, here the abstraction process proceeds in reverse: the methodology does not abstract models;rather it models abstractions. Specifically, it first formalizes a template for a family of stochastic abstractions, and then fits the parameters of that template to match the dynamics of the underlying process and ground the abstraction. The article also shows how the parameter-fitting approach can be implemented based on a probabilistic model validation approach which draws from randomized algorithms, and results in a discrete abstract model which is approximately simulated by the actual process physics, at a desired confidence level. In this way, the models afford the implementation of symbolic control plans with probabilistic guarantees at a desired level of fidelity.

关键词： Robots Markov processes Probabilistic logic Process control Mathematical models Aerospace electronics Physics Discrete abstractions randomized algorithms simulation relations stochastic processes

来源：评论

学校读者我要写书评

暂无评论

Optimal Parallel Sorting with Comparison Errors 23

Optimal Parallel Sorting with Comparison Errors

引用

35th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Goodrich, Michael T. Jacob, Riko Univ Calif Irvine Irvine CA 92697 USA IT Univ Copenhagen Copenhagen Denmark

ISBN: (纸本)9781450395458

We present comparison-based parallel algorithms for sorting n comparable items subject to comparison errors. We consider errors to occur according to a well-studied framework, where the comparison of two elements returns the wrong answer with a fixed probability. In the persistent model, the result of the comparison of two given elements, x and y, always has the same result, and is independent of all other pairs of elements. In the non-persistent model, the result of the comparison of each pair of elements, x and y, is independent of all prior comparisons, including for x and y. It is not possible to always correctly sort a given input set in the persistent model, so we study algorithms that achieve a small maximum dislocation and small total dislocation of the elements in the output permutation. In this paper, we provide parallel algorithms for sorting with comparison errors in the persistent and non-persistent models. Our algorithms are asymptotically optimal in terms of their span, work, and, in the case of persistent errors, maximum and total dislocation. The main results are algorithms for the binary-forking parallel model with atomics, but we also provide algorithms for the CREW PRAM model. Our algorithms include a number of novel techniques and analysis tools, including a PRAM-to-binary-forking-model simulation result, and are the first optimal parallel algorithms for the persistent model and the non-persistent model in the binary-forking parallel model with atomics. In particular, our algorithms haveO(log n) span, O(n log n) work, and, in the case of the persistent model, O(log n) maximum dislocation and O(n) total dislocation, with high probability. We achieve similar results for the CREW PRAM model, which are the first optimal methods for the persistent model and the first optimal results for the non-persistent model with reasonable constant factors in the performance bounds.

关键词： sorting noisy searching algorithm analysis randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimizing the Critical Path of Distributed Dataflow Graph algorithms

Optimizing the Critical Path of Distributed Dataflow Graph A...

引用

37th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Durrman, Dante Saule, Erik UNC Charlotte Dept Math Charlotte NC 28223 USA UNC Charlotte Dept Comp Sci Charlotte NC 28223 USA

ISBN: (纸本)9798350311990

Executing graph algorithms in a parallel or distributed context is a challenging problem. Solving race conditions with locks is usually prohibitively expensive and some algorithms opt for a strategy that ignores the race condition altogether and corrects later the derived solution if it is invalid. Alternatively, dataflow algorithms solve the synchronization problem by executing the algorithm by following a partial order on the graph. While removing the cost of locks or avoiding a checking phase improves performance, it is possible that the algorithm picks a partial order with long chains, which limit parallelism. In this paper, we investigate how distributed dataflow graph algorithm obtain a partial order and how one could favor orders with shorter long chains. Most dataflow algorithms obtain their order by having each vertex of the graph pick a uniformly random number in [0;1) and order the vertices based on that number. We believe that this type of order could lead to long chains in graphs with dense regions such as small world graph. We design two alternative ways of generating the order to make it similar to a largest degree first order. We study the behavior of these different algorithms on a wide range of randomly generated RMAT graphs and on a set of real world graphs. And we show that our ordering methods can significantly reduce the length of the longest chain.

关键词： graph analysis distributed computing partial order interval coloring randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Query Algorithm for Learning a Spanning Forest in Weighted Undirected Graphs 34

A Query Algorithm for Learning a Spanning Forest in Weighted...

引用

34th International Conference on Algorithmic Learning Theory (ALT)

作者： Chakrabarty, Deeparnab Liao, Hang Dartmouth Coll Dept Comp Sci Hanover NH 03755 USA

We consider the problem of finding a spanning forest in an unknown weighted undirected graph when the access to the graph is via CUT queries, that is, one can query a subset S subset of V of vertices and get the cut-value Sigma(e is an element of partial derivative S) omega(e) as the response. It is not too hard to solve this problem using O(n log n) queries mimicking a Prim-style algorithm using a binary-search style idea. In this paper we use the power of CUT queries to obtain a Monte-Carlo algorithm that makes O(n log log n(log log log n)(2)) CUT queries. At the core of our contribution is a generalization of a result in [Apers et al., 2022] which studies the same problem on unweighted graphs, but to handle weights, we need to combine their ideas with ideas for support estimation of weighted vectors, as in [Stockmeyer, 1983], and weighted graph reconstruction algorithms, as in [Bshouty and Mazzawi, 2012].

关键词： Query algorithms Weighted Spanning Forest randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：