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

A Latent Factor Analysis-Based Approach to online Sparse Streaming Feature Selection

IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS 2022年第11期52卷 6744-6758页

作者： Wu, Di He, Yi Luo, Xin Zhou, MengChu Chinese Acad Sci Chongqing Engn Res Ctr Big Data Applicat Smart Ci Chongqing 400714 Peoples R China Chinese Acad Sci Chongqing Inst Green & Intelligent Technol Chongqing Key Lab Big Data & Intelligent Comp Chongqing 400714 Peoples R China Old Dominion Univ Dept Comp Sci Norfolk VA 23462 USA Cloudwalk Dept Big Data Anal Tech Hengrui Chongqing Artificial Intelligence Res Ctr Chongqing 401331 Peoples R China New Jersey Inst Technol Helen & John C Hartmann Dept Elect & Comp Engn Newark NJ 07102 USA Macau Univ Sci & Technol Inst Syst Engn Macau 999078 Peoples R China Macau Univ Sci & Technol Collaborat Lab Intelligent Sci & Syst Macau 999078 Peoples R China

online streaming feature selection (OSFS) has attracted extensive attention during the past decades. Current approaches commonly assume that the feature space of fixed data instances dynamically increases without any missing data. However, this assumption does not always hold in many real applications. Motivated by this observation, this study aims to implement online feature selection from sparse streaming features, i.e., features flow in one by one with missing data as instance count remains fixed. To do so, this study proposes a latent-factor-analysis-based online sparse-streaming-feature selection algorithm (LOSSA). Its main idea is to apply latent factor analysis to pre-estimate missing data in sparse streaming features before conducting feature selection, thereby addressing the missing data issue effectively and efficiently. Theoretical and empirical studies indicate that LOSSA can significantly improve the quality of OSFS when missing data are encountered in target instances.

关键词： Big data computational intelligence latent factor analysis (LFA) missing data online algorithm online feature selection sparse streaming feature streaming feature

来源：评论

学校读者我要写书评

暂无评论

online inventory replenishment scheduling of temporary orders

引用

INFORMATION PROCESSING LETTERS 2013年第5-6期113卷 188-192页

作者： Yu, Haiyan Xu, Yinfeng Wu, Tengyu Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Peoples R China

This paper studies the online inventory replenishment scheduling problem, in which orders from retailers arrive and depart at arbitrary times at one supplier and each order needs to be replenished at least once every constant periods. The supplier needs to assign each order to some vehicle such that the maximum number of vehicles ever used over all time is minimized, while each vehicle can replenish only one order per period. We present a Combined First Fit algorithm and improve the upper bound of the competitive ratio for this problem to be 3.0913 from 5. When offline algorithm is unrestricted, the Combined First Fit algorithm is proved to be 6.1826-competitive. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Replenishment Scheduling online algorithm Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

online scheduling to minimize total weighted (modified) earliness and tardiness cost

引用

JOURNAL OF SCHEDULING 2021年第4期24卷 431-446页

作者： Jabbari, Arman Kaminsky, Philip M. Univ Calif Berkeley Ind Engn & Operat Res 4141 Etcheverry Hall Berkeley CA 94720 USA

We formulate a single machine online scheduling problem where jobs with distinct processing times, weights, and due dates arrive over time and must be processed one at a time without preemption in order to minimize the total weighted earliness and tardiness cost. We introduce a new scheduling policy, the list-based delayed shortest processing time (LDWSPT) policy, which is amenable to theoretical analysis. We develop lower and upper bounds on the performance of the LDWSPT policy for the minimization of total weighted (modified) earliness and tardiness cost for the case of equal earliness and tardiness costs, and then extend our results for the case when these costs are not equal. Finally, we close the optimality gap that currently exists in the literature for several variants of single machine online scheduling problems in the presence of earliness and tardiness by proving that our proposed policy is an optimal online algorithm for these variants.

关键词： online scheduling Single machine online algorithm Competitive analysis Competitive ratio Earliness and tardiness

来源：评论

学校读者我要写书评

暂无评论

Optimal solutions for the online time series search and one-way trading problem with interrelated prices and a profit function

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2018年 119卷 465-471页

作者： Schroeder, Pascal Dochow, Robert Schmidt, Guenter Saarland Univ Dept Operat Res & Business Informat Saarbrucken Germany Univ Cape Town Dept Finance & Tax Cape Town South Africa

We consider the online problems of time series search and one-way trading with interrelated prices. We derive two algorithms PUND and PDIV which extend the solutions found in literature with profit functions, derive the competitive ratio and prove optimality. For the new as well as for the established online algorithms, we give a numerical example. For the time series search problem with interrelated prices, we present another algorithm UND*. This algorithm has constant time complexity and an explicit formula for the competitive ratio and selected period to sell. The current solution in literature has linear time complexity and no such explicit formulas.

关键词： Time series search One-way trading online algorithm Competitive analysis Profit function Interrelated prices

来源：评论

学校读者我要写书评

暂无评论

online Bounds on Balancing Two Independent Criteria with Replication and Reallocation

引用

IEEE TRANSACTIONS ON COMPUTERS 2012年第11期61卷 1601-1610页

作者： Tse, Savio S. H. Istanbul Univ Dept Comp Engn TR-34320 Istanbul Turkey

We study the online bicriteria load balancing problem in this paper. We choose a system of distributed homogeneous file servers located in a cluster as the scenario and propose three online approximate solutions for balancing their loads and required storage spaces upon placements. We first revisit the best existing solution for simple placement (i.e., without replication and reallocation), and rewrite it in our first algorithm by imposing some flexibilities. Our second algorithm is to apply document replication. The upper bound of load is significantly reduced, without sacrificing that of the storage space. This upper bound contains at least one special case which can never be outperformed by any online simple placement algorithms. Lastly, we show that there exists an online algorithm which allows very little document reallocation, but gives an upper bound result on the load and storage space, which is never reachable by any online algorithms for simple placement. The time complexities of the first two algorithms are in O(log M), and the last algorithm runs in O(log MN) time, where M is the number of servers, and N is the number of existing documents.

关键词： Approximate distributed online algorithm load balancing scheduling distributed file server document placement replication reallocation

来源：评论

学校读者我要写书评

暂无评论

An online Auction Mechanism for Dynamic Virtual Cluster Provisioning in Geo-Distributed Clouds

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2017年第3期28卷 677-688页

作者： Shi, Weijie Wu, Chuan Li, Zongpeng Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada

It is common for cloud users to require clusters of inter-connected virtual machines (VMs) in a geo-distributed IaaS cloud, to run their services. Compared to isolated VMs, key challenges on dynamic virtual cluster (VC) provisioning (computation + communication resources) lie in two folds: (1) optimal placement of VCs and inter-VM traffic routing involve NP-hard problems, which are non-trivial to solve offline, not to mention if an online efficient algorithm is sought;(2) an efficient pricing mechanism is missing, which charges a market-driven price for each VC as a whole upon request, while maximizing system efficiency or provider revenue over the entire span. This paper proposes efficient online auction mechanisms to address the above challenges. We first design SWMOA, a novel online algorithm for dynamic VC provisioning and pricing, achieving truthfulness, individual rationality, computation efficiency, and (1 + 2 log mu)-competitiveness in social welfare, where m is related to the problem size. Next, applying a randomized reduction technique, we convert the social welfare maximizing auction into a revenue maximizing online auction, PRMOA, achieving O(log mu)-competitiveness in provider revenue, as well as truthfulness, individual rationality and computation efficiency. We investigate auction design in different cases of resource cost functions in the system. We validate the efficacy of the mechanisms through solid theoretical analysis and trace-driven simulations.

关键词： Cloud computing auction mechanism design online algorithm resource allocation

来源：评论

学校读者我要写书评

暂无评论

online scheduling with equal processing times and machine eligibility constraints

引用

THEORETICAL COMPUTER SCIENCE 2015年 572卷 58-65页

作者： Xu, Jia Liu, Zhaohui E China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

We consider the online scheduling problem on m parallel machines with eligibility constraints. The jobs arrive over time and have equal processing times. The objective is to minimize the makespan. We develop optimal deterministic online algorithms for the nested processing set case and the inclusive processing set case with an arbitrary number of machines, as well as the tree-like processing set case with three machines. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Scheduling Parallel machine Eligibility constraint online algorithm

来源：评论

学校读者我要写书评

暂无评论

A new lower bound for online strip packing

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2016年第3期250卷 754-759页

作者： Yu, Guosong Mao, Yanling Xiao, Jiaoliao Nanchang Univ Dept Math Nanchang 330031 Peoples R China Nanchang Univ Dept Management Sci & Engn Nanchang 330031 Peoples R China

In this paper, we consider the online strip packing problem, in which a list of online rectangles has to be packed without overlap or rotation into a strip of width 1 and infinite length so as to minimize the required height of the packing. We derive a new improved lower bound of (3 + root 5)/2 approximate to 2.618 for the competitive ratio for this problem. This result improves the best known lower bound of 2.589. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.

关键词： Packing Strip packing online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online BIN PACKING OF ITEMS OF RANDOM SIZES .2.

引用

SIAM JOURNAL ON COMPUTING 1993年第6期22卷 1251-1256页

作者： RHEE, WT TALAGRAND, M UNIV PARIS 06 CNRSEUROPEAN RES ASSOCIATESEQUIPE ANAL 294F-75230 PARIS 05FRANCE OHIO STATE UNIV DEPT MATHCOLUMBUSOH 43210

This paper describes the construction of an on-line algorithm with the following property. There exist universal constants K, alpha such that given any probability measure mu on [0, 1] and a sequence X(1),..., X(n),... of items independently and identically distributed according to mu, the algorithm packs X(1),...,X(n) into at most T-n((1),...,X(n)) + Kn(1/2)(log n)(3/4) unit-size bins, where T-n(X(1),...,X(n)) denotes the minimum number of bins needed to pack X(1),...,X(n), and does this with probability greater than or equal to 1 - K exp(-alpha(log n)(3/2). In contrast with the authors' previous work on this problem, the algorithm is now independent of mu.

关键词： STOCHASTIC BIN PACKING online algorithm

来源：评论

学校读者我要写书评

暂无评论

Formulating Cost-Effective Data Distribution Strategies online for Edge Cache Systems

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2022年第12期33卷 4270-4281页

作者： Xia, Xiaoyu Chen, Feifei He, Qiang Grundy, John Abdelrazek, Mohamed Shen, Jun Bouguettaya, Athman Jin, Hai Univ Adelaide Sch Comp Sci Adelaide SA 5005 Australia Deakin Univ Sch Informat Technol Burwood Vic 3125 Australia Swinburne Univ Technol Dept Comp Technol Hawthorn Vic 3122 Australia Monash Univ Fac Informat Technol Clayton Vic 3800 Australia Univ Wollongong Sch Comp & Informat Technol Wollongong NSW 2522 Australia Univ Sydney Sch Comp Sci Camperdown NSW 2006 Australia Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430074 Hubei Peoples R China

Edge Computing (EC) enables a new kind of caching system in close geographic proximity to end-users by allowing app vendors to cache popular data on edge servers deployed at base stations. This edge cache system can better support latency-sensitive applications. However, transmitting data from the centralized cloud to the edge servers without proper transmission strategies may cost app vendors dearly. Cost-effective data distribution strategies are of particular importance for applications, whose data to be cached at the edge often changes dynamically. In this paper, we study this online Edge Data Distribution (OEDD) problem, aiming to minimize app vendors' total transmission cost, while ensuring low transmission latency in the long term. We first model this problem and prove its NP-hardness. We then combine Lyapunov optimization and game theory to propose a novel Latency-Aware online (LAO) approach for solving this OEDD problem over time in a distributed manner with provable performance guarantees. The evaluation of LAO based on a real-world dataset demonstrates that it can help app vendors formulate cost-effective edge data distribution strategies in an online manner.

关键词： Data distribution edge cache system online algorithm optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：