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

online kernel-based classification using adaptive projection algorithms

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2008年第7期56卷 2781-2796页

作者： Slavakis, Konstantinos Theodoridis, Sergios Yamada, Isao Univ Peloponnese Dept Telecommun Sci & Technol Tripoli 22100 Greece Univ Athens Dept Informat & Telecommun Athens 15784 Greece Tokyo Inst Technol Dept Commun & Integrated Syst Tokyo 1528552 Japan

The goal of this paper is to derive a novel online algorithm for classification in reproducing kernel hilbert spaces (RKHS) by exploiting projection-based adaptive filtering tools. The paper brings powerful convex analytic and set theoretic estimation arguments in machine learning by revisiting the standard kernel-based classification as the problem of finding: a point which belongs to a closed halfspace (a special closed convex set) in an RKHS. In this way, classification in an online setting, where data arrive sequentially, is viewed as the problem of finding a point (classifier) in the nonempty intersection of an infinite sequence of closed halfspaces in the RKHS. Convex analysis is also used to introduce sparsification arguments in the design by imposing an additional simple convex constraint on the norm of the classifier. An algorithmic solution to the resulting optimization problem, where new convex constraints are added every time instant, is given by the recently introduced adaptive projected subgradient method (APSM), which generalizes a number of well-known projection-based adaptive filtering algorithms such as the classical normalized least mean squares (NLMS) and the affine projection algorithm (APA). Under mild conditions, the generated sequence of estimates enjoys monotone approximation, strong convergence, asymptotic optimality, and a characterization of the limit point. Further, we show that the additional convex constraint on the norm of the classifier naturally leads to an online sparsification of the resulting kernel series expansion. We validate the proposed design by considering the adaptive equalization problem of a nonlinear channel, and by comparing it with classical as well as with recently developed stochastic gradient descent techniques.

关键词： adaptive filtering convex analysis kernel methods online algorithms projections

来源：评论

学校读者我要写书评

暂无评论

algorithms for the relaxed online bin-packing model

引用

SIAM JOURNAL ON COMPUTING 2000年第5期30卷 1532-1551页

作者： Gambosi, G Postiglione, A Talamo, M Univ Roma Tor Vergata Dipartimento Matemat I-00133 Rome Italy Univ Salerno Dipartimento Sci Comunicaz I-84084 Rome Italy Univ Rome La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy

The typical online bin-packing problem requires the fitting of a sequence of rationals in (0, 1] into a minimum number of bins of unit capacity, by packing the ith input element without any knowledge of the sizes or the number of input elements that follow. Moreover, unlike typical online problems, this one issue does not admit any data reorganization, i.e., no element can be moved from one bin to another. In this paper, rst of all, the Relaxed online bin-packing model will be formalized;this model allows a constant number of elements to move from one bin to another, as a consequence of the arrival of a new input element. Then, in the context of this new model, two online algorithms will be described. The first presents linear time and space complexities with a 1.5 approximation ratio and moves, at most once, only small elements;the second, instead, is an O (n log n) time and linear space algorithm with a 1.33... approximation ratio and moves each element a constant number of times. In the worst case, as a result of the arrival of a new input element, the rst algorithm moves no more than three elements, while the second moves as many as seven elements. Please note that the number of movements performed is explicitly considered in the complexity analysis. Both algorithms are below the theoretical 1. 536... lower bound, effective for the online bin-packing algorithms without the movement of elements. Moreover, our algorithms are more online than any other linear space online bin-packing algorithm because, unlike the algorithms already known, they allow the return of a ( possibly relevant) fraction of bins before the work is carried out.

关键词： complexity approximation algorithms online algorithms bin packing

来源：评论

学校读者我要写书评

暂无评论

online Electricity Cost Saving algorithms for Co-Location Data Centers

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2015年第12期33卷 2906-2919页

作者： Zhang, Linquan Li, Zongpeng Wu, Chuan Ren, Shaolei Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada Wuhan Univ Sch Comp Wuhan 430072 Peoples R China Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China Univ Calif Riverside Dept Elect & Comp Engn Riverside CA 92521 USA

This work studies the online electricity cost minimization problem at a co-location data center, which serves multiple tenants who rent the physical infrastructure within the data center to run their respective cloud computing services. The co-location operator has no direct control over power consumption of its tenants, and an efficient mechanism is desired for eliciting desirable consumption patterns from the tenants. Electricity billing faced by a data center is nowadays based on both the total volume consumed and the peak consumption rate. This leads to an interesting new combinatorial optimization structure on the electricity cost optimization problem, which also exhibits an online nature due to the definition of peak consumption. We model and solve the problem through two approaches: the pricing approach and the auction approach, and design online algorithms with small competitive ratios.

关键词： Co-location data centers mechanism design online algorithms

来源：评论

学校读者我要写书评

暂无评论

Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching

引用

THEORETICAL COMPUTER SCIENCE 2015年第Part2期607卷 247-256页

作者： Ting, H. F. Xiang, Xiangzhong Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

This paper studies the online maximum edge-weighted b-matching problem. The input of the problem is a weighted bipartite graph G = (L, R, E, w). Vertices in R arrive online, and each vertex in L can be matched to at most b vertices in R. The objective is to maximize the total weight of the matching edges. We give a randomized algorithm GREEDY-RT for this problem, and show that its competitive ratio is Omega(1/Pi(log*wmax-1)(J=1) log((j)) w(max)) where w(max) is an upper bound on the edge weights, which may not be known ahead of time. We can improve the competitive ratio to Omega(1/logw(max)) if w(max) is known to the algorithm when it starts. We also derive an upper bound O(1/logw(max)) on the competitive ratio, suggesting that GREEDY-RT is near optimal. We also consider deterministic algorithms;we present a near optimal algorithm GREEDY-D which has competitive ratio 1/1+2 xi(w(max)+1)(1/xi) where xi = min{b, left perpendicular ln(1 + w(max))right perpendicular}. We also study a variant of the problem called online maximum two-sided vertex-weighted b-matching problem, and give a modification of the randomized algorithm GREEDY-RT called GREEDY-vRT for this variant. We show that the competitive ratio of GREEDY-vRT is also near optimal. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Maximum weighted matching online algorithms Competitive analysis Upper and lower bounds

来源：评论

学校读者我要写书评

暂无评论

On the competitive theory and practice of online list accessing algorithms

引用

ALGORITHMICA 2002年第2期32卷 201-246页

作者： Bachrach, R El-Yaniv, R Reinstädtler, M Hebrew Univ Jerusalem Inst Comp Sci Jerusalem Israel Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Max Planck Inst Informat D-66401 Saarbrucken Germany

This paper concerns the online list accessing problem. In the first part of the paper we present two new families of list accessing algorithms. The first family is of optimal, 2-competitive, deterministic online algorithms. This family, called the MRI (MOVE-TO-RECENT-ITEM) family, includes as members the well-known MOVE-TO-FRONT (MTF) algorithm and the recent, more "conservative" algorithm TIMESTAMP due to Albers. So far MOVE-TO-FRONT and TIMESTAMP were the only algorithms known to be optimal in terms of their competitive ratio. This new family contains a sequence of algorithms {A(i)}(i greater than or equal to1) where A(1) is equivalent to TIMESTAMP and the limit element A (oo) is MTF. Further, in this class, for each i, the algorithm A (i) is more conservative than algorithm A (i + 1) in the sense that it is more reluctant to move an accessed item to the front, thus giving a gradual transition from the conservative TIMESTAMP to the "reckless" MTF. The second new family, called the PRI (PASS-RECENT-ITEM) family, is also infinite and contains TIMESTAMP. We show that most algorithms in this family attain a competitive ratio of 3. In the second, experimental, part of the paper we report the results of an extensive empirical study of the performances of a large set of online list accessing algorithms (including members of our MRI and PPI families). The algorithms' access cost performances were tested with respect to a number of different request sequences. These include sequences of independent requests generated by probability distributions and sequences generated by Markov sources to examine the influence of locality. It turns out that the degree of locality has a considerable influence on the algorithms' absolute and relative. costs, as well as on their rankings. In another experiment we tested the algorithms' performances as data compressors in two variants of the compression scheme of Bentley et al. In both experiments, members of the MRI and PRI families were fou

关键词： online algorithms list accessing list update self-organizing data structures competitive analysis lossless compression Calgary Corpus

来源：评论

学校读者我要写书评

暂无评论

online VM Auto-Scaling algorithms for Application Hosting in a Cloud

引用

IEEE TRANSACTIONS ON CLOUD COMPUTING 2020年第3期8卷 889-898页

作者： Guo, Yang Stolyar, Alexander L. Walid, Anwar NIST Gaithersburg MD 20899 USA Univ Illinois Champaign IL 61801 USA Nokia Bell Labs Murray Hill NJ 07974 USA

We consider the auto-scaling problem for application hosting in a cloud, where applications are elastic and the number of requests changes over time. The application requests are serviced by Virtual Machines (VMs), which reside on Physical Machines (PMs) in a cloud. We aim to minimize the number of hosting PMs by intelligently packing VMs into PMs, while the VMs are auto-scaled, i.e., dynamically acquired and released, to accommodate varying application needs. We consider a shadow routing based approach for this problem. The proposed shadow algorithm employs a specially constructed virtual queueing system to dynamically produce an optimal solution that guides the VM auto-scaling and the VM-to-PM packing. The proposed algorithm runs continuously without the need to re-solve the underlying optimization problem "from scratch", and adapts automatically to the changes in the application demands. We prove the asymptotic optimality of the shadow algorithm. The simulation experiments further demonstrate the algorithm's good performance and high adaptivity.

关键词： Cloud computing data centers auto-scaling virtual machine dynamic stochastic bin packing online algorithms

来源：评论

学校读者我要写书评

暂无评论

online force-directed algorithms for visualization of dynamic graphs

引用

INFORMATION SCIENCES 2021年 556卷 223-255页

作者： Cheong, Se-Hang Si, Yain-Whar Wong, Raymond K. Univ Macau Dept Comp & Informat Sci Macau Peoples R China Univ New South Wales Sch Comp Sci & Engn Sydney NSW Australia

Force-directed (FD) algorithms can be used to explore relationships in social networks, visualize money markets, and analyze transaction networks. However, FD algorithms are mainly designed for visualizing static graphs in which the topology of the networks remains constant throughout the calculation. In contrast to static graphs, nodes and edges in dynamic graphs can be added or removed as time progresses. In these situations, existing FD algorithms do not scale well, since any changes in the topology will trigger these algorithms to completely restart the entire computation. To alleviate this problem, we propose a design and implementation of five online FD algorithms to visualize dynamic graphs while maintaining their native force models. The online FD algorithms developed in this paper are able to reuse the force models of existing FD algorithms without significant modifications. To evaluate the effectiveness of the proposed approach, online FD algorithms are compared against static FD algorithms for visualizing dynamic graphs. Experimental results show that among the five algorithms evaluated, the online FD algorithm achieves the best number of edge crossings and the standard deviation of edge lengths for visualizing dynamic graphs. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Force-directed algorithms Visualization Dynamic graphs online algorithms

来源：评论

学校读者我要写书评

暂无评论

Preemptive online Scheduling: Optimal algorithms for All Speeds

引用

ALGORITHMICA 2009年第4期53卷 504-522页

作者： Ebenlendr, Tomas Jawor, Wojciech Sgall, Jiri Acad Sci Czech Republic Inst Math CR-11567 Prague 1 Czech Republic Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA

Our main result is an optimal online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize makespan. The algorithm is deterministic, yet it is optimal even among all randomized algorithms. In addition, it is optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various special cases. Together with a new lower bound it follows that the overall competitive ratio of this optimal algorithm is between 2.054 and e approximate to 2.718. We also give a complete analysis of the competitive ratio for three machines.

关键词： online algorithms Scheduling Makespan

来源：评论

学校读者我要写书评

暂无评论

THE COMPETITIVENESS OF RANDOMIZED algorithms FOR online STEINER TREE AND online SPANNING TREE PROBLEMS

引用

INFORMATION PROCESSING LETTERS 1993年第4期48卷 177-182页

作者： TSAI, YT TANG, CY NATL TSING HUA UNIV DEPT COMP SCIHSINCHU 300TAIWAN

This paper considers a family of randomized on-line algorithms, Algorithm R(m), where 1 less-than-or-equal-to m less-than-or-equal-to n - 1 and n is the number of input points, for the on-line Steiner tree and on-line spanning tree problems on Euclidean space. Our main result is that if m is a fixed constant, the competitive ratios of Algorithm R(m) for the on-line Steiner tree and spanning tree problems are THETA(n). We also show that the competitive ratio of Algorithm R(n - 1), which is deterministic greedy algorithm, for the on-line spanning tree problem is the same as that for the on-line Steiner tree problem, which is O(log n).

关键词： ANALYSIS OF algorithms online algorithms RANDOMIZED algorithms COMPETITIVE ANALYSIS online STEINER TREE PROBLEM online SPANNING TREE PROBLEM

来源：评论

学校读者我要写书评

暂无评论

algorithms for online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios

引用

OPERATIONS RESEARCH 2020年第6期68卷 1787-1803页

作者： Ma, Will Simchi-Levi, David Columbia Univ Grad Sch Business New York NY 10027 USA MIT Dept Civil & Environm Engn Inst Data Syst & Soc 77 Massachusetts Ave Cambridge MA 02139 USA MIT Operat Res Ctr 77 Massachusetts Ave Cambridge MA 02139 USA

Motivated by the dynamic assortment offerings and item pricings occurring in e-commerce, we study a general problem of allocating finite inventories to heterogeneous customers arriving sequentially. We analyze this problem under the framework of competitive analysis, where the sequence of customers is unknown and does not necessarily follow any pattern. Previous work in this area, studying online matching, advertising, and assortment problems, has focused on the case where each item can only be sold at a single price, resulting in algorithms which achieve the best-possible competitive ratio of 1-1/e. In this paper, we extend all of these results to allow for items havingmultiple feasible prices. Our algorithms achieve the best-possible weight-dependent competitive ratios, which depend on the sets of feasible prices given in advance. Our algorithms are also simple and intuitive;they are based on constructing a class of universal value functions that integrate the selection of items and prices offered. Finally, we test our algorithms on the publicly available hotel data set of Bodea et al. [Bodea T, Ferguson M, Garrow L (2009) Data set-Choice-based revenue management: Data from a major hotel chain. Manufacturing Service Oper. Management 11(2):356-361.], where there are multiple items (hotel rooms), each with multiple prices (fares at which the room could be sold). We find that applying our algorithms, as a hybrid with algorithms that attempt to forecast and learn the future transactions, results in the best performance.

关键词： online algorithms revenue management online matching Adwords

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：