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

42nd ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Emiris, Ioannis Z. Konaxis, Christos Kotsireas, Ilias S. Laroche, Clement Univ Athens Dept Informat & Telecommun Maroussi Greece ATHENA Res Ctr Maroussi Greece Wilfrid Laurier Univ Dept Phys & Comp Sci Waterloo ON Canada

ISBN: (纸本)9781450350648

We examine implicit representations of parametric or point cloud models, based on interpolation matrices, which are not sensitive to base points. We show how interpolation matrices can be used for ray shooting of a parametric ray with a surface patch, including the case of high-multiplicity intersections. Most matrix operations are executed during pre-processing since they solely depend on the surface. For a given ray, the bottleneck is equation solving. Our Maple code handles bicubic patches in <= 1 sec, though numerical issues might arise. Our second contribution is to extend the method to parametric space curves and, generally, to codimension > 1, by computing the equations of (hyper)surfaces intersecting precisely at the given object. By means of Chow forms, we propose a new, practical, randomized algorithm that always produces correct output but possibly with a non-minimal number of surfaces. For space curves, we typically obtain 3 surfaces whose polynomials are of near-optimal degree;in this case, computation reduces to a Sylvester resultant. Our Maple prototype is not faster but yields fewer equations and seems more robust than Maple's implicitize.

关键词： Matrix representation sparse resultant Chow form ray shooting randomized algorithm implicitization space curve Maple implementation

来源：评论

学校读者我要写书评

暂无评论

A randomized Reputation System in the Presence of Unfair Ratings

引用

ACM TRANSACTIONS ON MANAGEMENT INFORMATION SYSTEMS 2020年第1期11卷 2-2页

作者： Rezvani, Mohsen Rezvani, Mojtaba Shahrood Univ Technol Fac Comp Engn Shahrood *** Iran Australian Natl Univ Coll Engn & Comp Sci Canberra ACT 2601 Australia

With the increasing popularity of online shopping markets, a significant number of consumers rely on these venues to meet their demands while choosing different products based on the ratings provided by others. Simultaneously, consumers feel confident in expressing their opinions through ratings. As a result, millions of ratings are generated on the web for different products, services, and dealers. Nonetheless, a noticeable number of users post unfair feedback. Recent studies have shown that reputation escalation is emerging as a new service, by which dealers pay to receive good feedback and escalate their ratings in online shopping markets. Therefore, finding robust and reliable ways to distinguish between fake and trustworthy ratings from users is a crucial task for every online shopping market. Moreover, with the dramatic increase in the number of ratings provided by consumers, scalability has arisen as another significant issue in the existing methods of reputation systems. To tackle these issues, we propose a randomized algorithm that calculates the reputation based on a random sample of the ratings. Since the randomly selected sample has a logarithmic size, it guarantees feasible scalability for large-scale online review systems. In addition, the randomness nature of the algorithm makes it robust against unfair ratings. We provide a thorough theoretical analysis of the proposed algorithm and validate its effectiveness through extensive empirical evaluation using real-world and synthetically generated datasets. Our experimental results show that the proposed method provides a high accuracy while running much faster than the existing iterative filtering approaches.

关键词： Reputation system data aggregation randomized algorithm trust computation online rating

来源：评论

学校读者我要写书评

暂无评论

MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization 3

MURANA: A Generic Framework for Stochastic Variance-Reduced ...

引用

3rd Annual Conference on Mathematical and Scientific Machine Learning

作者： Condat, Laurent Richtarik, Peter King Abdullah Univ Sci & Technol Thuwal 239556900 Saudi Arabia

We propose a generic variance-reduced algorithm, which we call MUltiple randomized algorithm (MURANA), for minimizing a sum of several smooth functions plus a regularizer, in a sequential or distributed manner. Our method is formulated with general stochastic operators, which allow us to model various strategies for reducing the computational complexity. For example, MURANA supports sparse activation of the gradients, and also reduction of the communication load via compression of the update vectors. This versatility allows MURANA to cover many existing randomization mechanisms within a unified framework, which also makes it possible to design new methods as special cases.

关键词： convex optimization distributed optimization randomized algorithm stochastic gradient variance reduction communication sampling compression

来源：评论

学校读者我要写书评

暂无评论

Secure Communication Over Radio Channels

Secure Communication Over Radio Channels

引用

27th Annual ACM Symposium on Principles of Distributed Computing

作者： Dolev, Shlomi Gilbert, Seth Guerraoui, Rachid Newport, Calvin Ben Gurion Univ Negev IL-84105 Beer Sheva Israel EPFL IC Lausanne Switzerland MIT CSAIL Cambridge MA USA

ISBN: (纸本)9781595939890

We study the problem of secure communication in a multichannel, single-hop radio network with a malicious adversary that, call cause collisions and spoof messages. We assume no pre-shared secrets or trusted-third-party infrastructure. The main contribution of this paper is f-AME: a randomized (f)ast-(A)uthenticated (M)essage (E)xchange protocol that enables nodes to exchange messages in a reliable and anthenticated manner. It runs in O(vertical bar E vertical bar t(2) log n) time and has optimal resilience to disruption, where E is the set of pairs of nodes that need to swap messages, n is the total number of nodes, C the number of channels, and t < C the number of channels on which the adversary can participate in each round. We show how to use f-AME to establish a shared secret group key, which can be used to implement a secure, reliable and authenticated long-lived communication service. The resulting service requires O(nt(3) log n) rounds for the setup phase, and O(t log n) rounds for an arbitrary pair to communicate. By contrast, existing solutions rely on pre-shared secrets, trusted third-party infrastructure, and/or the assumption that all interference is non-malicious.

关键词： Wireless Radio Networks Malicious (Byzantine) Interference randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Discrete Load Balancing is (almost) as Easy as Continuous Load Balancing

Discrete Load Balancing is (almost) as Easy as Continuous Lo...

引用

29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

作者： Elsaesser, Robert Sauerwald, Thomas Univ Freiburg Inst Comp Sci D-79110 Freiburg Germany

ISBN: (纸本)9781605588889

We consider the problem of diffusion-based load balancing on a distributed network with n processors. If the load is arbitrarily divisible, then the convergence is fairly well captured in terms of the second largest eigenvalue of the diffusion matrix. As for many applications load can not be arbitrarily divided, we consider a model where load consists of indivisible, unit-size tokens. Quantifying by how much this integrality assumption worsens the efficiency of load balancing algorithms is a natural question which has been posed by many authors [9, 15, 16, 19, 6, 17]. In this paper we show essentially that discrete load balancing is almost as easy as continuous load balancing. More precisely, we present a fully distributed, randomized algorithm for discrete load balancing that balances the load up to an additive constant error on any graph in time O(log(Kn)/(1-lambda(2))), where K is the initial imbalance and lambda(2) is the second largest eigenvalue of the diffusion matrix. This improves and tightens a result of Elsasser, Monien, Schamberger (2006) who proved a runtime bound of O((log(K) + (log n)(2))/(1-lambda(2))). We also develop a load balancing algorithm based on routing that achieves a runtime of O(D . log n), where D is the diameter of the graph.

关键词： Load Balancing randomized algorithm Random Walks

来源：评论

学校读者我要写书评

暂无评论

A Simulated Annealing based Energy Efficient Task Scheduling algorithm for Multi-core Processors 13th

A Simulated Annealing based Energy Efficient Task Scheduling...

引用

13th International Joint Conference on Computational Intelligence (IJCCI) / 13th International Conference on Evolutionary Computation Theory and Applications (ECTA)

作者： Pratik, S. Mishra, Abhishek Birla Inst Technol & Sci Pilani Dept Comp Sci & Informat Syst Pilani Rajasthan India

ISBN: (纸本)9789897585340

In this paper we propose a Simulated Annealing (SA) based energy-efficient task scheduling algorithm for multi-core processors, the Simulated Annealing Energy Efficient Task Scheduling algorithm (SAEETSA), and compare it with another algorithm, the Energy Efficient Task Scheduling algorithm (EETSA). Our results show that for dual-core processors the SAEETSA algorithm is taking up to 16.78% less energy as compared to the EETSA algorithm, and for tri-core processors, the SAEETSA algorithm is taking up to 26.97% less energy as compared to the EETSA algorithm.

关键词： Multi-core Processors randomized algorithm Scheduling Simulated Annealing Task Allocation

来源：评论

学校读者我要写书评

暂无评论

An Improved PTAS approximation algorithm for k-means Clustering Problem

An Improved PTAS approximation Algorithm for k-means Cluster...

引用

2nd International Conference on Uncertainty Reasoning and Knowledge Engineering (URKE)

作者： Wang Shouqiang Shanghai Jiao Tong Univ Dept Informat Engn Jinan 250023 Peoples R China

ISBN: (纸本)9781467314602

This paper presented an improved (1+epsilon)-randomized approximation algorithm proposed by Ostrovsky. The running time of the improved algorithm is O(2(O(k alpha 2/epsilon)) nd), where d,n denote the dimension and the number of the input points respectively, and alpha(<1) represents the separated coefficient. The successful probability is (1/2(1 - e((-1/2 epsilon))))(k)(1 - O(root alpha)). Compared to the original algorithm, the improved algorithm runs more efficiency.

关键词： Algorith randomized algorithm Clustering Centroid

来源：评论

学校读者我要写书评

暂无评论

On Approximating the d-Girth of a Graph

On Approximating the <i>d</i>-Girth of a Graph

引用

37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011

作者： Peleg, David Sau, Ignasi Shalom, Mordechai Weizmann Inst Sci Dept Comp Sci IL-76100 Rehovot Israel CNRS LIRMM AlGCo project team Montpellier France TelHai Acad Coll IL-12210 Upper Galilee Israel

ISBN: (纸本)9783642183805

For a finite, simple, undirected graph G and an integer d >= 1, a mindeg-d subgraph is a subgraph of G of minimum degree at least d. The d-girth of G, denoted g(d)(G), is the minimum size of a mindeg-d subgraph of G. It is a natural generalization of the usual girth, which coincides with the 2-girth. The notion of d-girth was proposed by Erdos et al. [13, 14] and Bollobas and Brightwell [7] over 20 years ago, and studied from a purely combinatorial point of view. Since then, no new insights have appeared in the literature. Recently, first algorithmic studies of the problem have been carried out [2,4]. The current article further explores the complexity of finding a small mindeg-d subgraph of a given graph (that is, approximating its d-girth), by providing new hardness results and the first approximation algorithms in general graphs, as well as analyzing the case where G is planar.

关键词： generalized girth minimum degree approximation algorithm hardness of approximation randomized algorithm planar graph

来源：评论

学校读者我要写书评

暂无评论

DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead 20

DConstructor: Efficient and Robust Network Construction with...

引用

39th Symposium on Principles of Distributed Computing

作者： Gilbert, Seth Pandurangan, Gopal Robinson, Peter Trehan, Amitabh Natl Univ Singapore Dept Comp Sci Singapore Singapore Univ Houston Dept Comp Sci Houston TX 77004 USA City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Loughborough Univ Dept Comp Sci Loughborough Leics England

ISBN: (纸本)9781450375825

With the rise of dynamic reconfigurable networks such as Peer-to-Peer (P2P) networks, overlay networks, ad hoc wireless and mesh networks, it has become important to construct and maintain topologies with various desirable properties (such as connectivity, low diameter, expansion, low degree etc.) in an efficient decentralized manner. The main result of this paper is a distributed protocol called DConstructor that given any (connected) network topology will "converge" to a given (desired) target topology such as an expander, hypercube, or Chord, with high probability. Our protocol is efficient, lightweight, and scalable, and it incurs only O (polylog(n)) overhead (where.. is the network size) for topology construction and maintenance: only polylogarithmic (in n) bits need to be processed and sent by each node per round, the convergence time is polylogarithmic rounds and any node's computation cost per round is also polylogarithmic. Our protocol is robust and self-repairing in the sense that it will converge to the desired topology in polylogarithmic rounds and polylogarithmic communication cost under dynamic topology changes and arbitrary insertions and deletions of nodes.

关键词： Distributed Protocol Peer-to-Peer Network randomized algorithm Self-repairing Network Expander

来源：评论

学校读者我要写书评

暂无评论

Improved Sublinear Primal-Dual algorithm for Support Vector Machines 11th

Improved Sublinear Primal-Dual Algorithm for Support Vector ...

引用

11th International Conference on Knowledge Science, Engineering and Management (KSEM)

作者： Gu, Ming Liao, Shizhong Tianjin Univ Sch Comp Sci & Technol Tianjin 300350 Peoples R China

ISBN: (纸本)9783319992471;9783319992464

Sublinear primal-dual algorithm (SUPDA) is a well established sublinear time algorithm. However, SUPDA performs the primal step in every iteration, which is unnecessary since the overall regret of SUPDA is dominated by the dual step. To improve the efficiency of SUPDA, we propose an improved SUPDA (ISUPDA), and apply ISUPDA to linear support vector machines, which yields an improved sublinear primal-dual algorithm for linear support vector machines (ISUPDA-SVM). Specifically, different from SUPDA that conducts the primal step in every iteration, ISUPDA executes the primal step with a probability at each iteration, which can reduce the time complexity of SUPDA. We prove that the expected regret of ISUPDA is still dominated by the dual step and hence ISUPDA guarantees the convergence. We further convert linear support vector machines into saddle-point forms in order to apply ISUPDA to linear support vector machines, and provide the theoretical guarantee of the quality of solution and efficiency for ISUPDA-SVM. Comparison experiments on multiple datasets demonstrate that ISUPDA outperforms SUPDA and that ISUPDA-SVM is an efficient algorithm for linear support vector machines.

关键词： Sublinear primal-dual algorithm Regret analysis randomized algorithm Linear support vector machines

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：