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

Optimal Offline and Competitive online Strategies for Transmitter-Receiver Energy Harvesting

IEEE TRANSACTIONS ON INFORMATION THEORY 2016年第8期62卷 4674-4695页

作者： Satpathi, Siddhartha Nagda, Rushil Vaze, Rahul Univ Illinois Dept Elect & Commun Engn Urbana IL 61801 USA IIT Roorkee Dept Appl Math Roorkee 247667 Uttar Pradesh India Tata Inst Fundamental Res Sch Technol & Comp Sci Bombay 400005 Maharashtra India

A joint transmitter-receiver energy harvesting model is considered, where both the transmitter and the receiver are powered by random (renewable) energy source. Given a fixed number of bits, the problem is to find the optimal transmission power profile at the transmitter and ON-OFF profile at the receiver to minimize the transmission time. With infinite capacity at both the transmitter and the receiver, the optimal offline and optimal online policies are derived. The optimal online policy is shown to be two-competitive in the arbitrary input case. With finite battery capacities at both ends, only random energy arrival sequence with given distribution is considered, for which an online policy with bounded expected competitive ratio is proposed.

关键词： Energy harvesting offline algorithm online algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

A preemptive truthful VMs allocation online mechanism in private cloud

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2016年 17卷 647-653页

作者： Gu, Yonggen Tao, Jie Li, Guoqiang Sun, Daniel W. Wu, Xiaohong Jayaraman, Prem Prakash Ranjan, Rajiv Huzhou Univ Sch Informat Engn Huzhou Peoples R China Shanghai Jiao Tong Univ Sch Software Shanghai Peoples R China CSIRO Data61 Canberra ACT Australia Univ New South Wales Sch Comp Sci & Engn Sydney NSW Australia Shanghai Univ Finance & Econ Shanghai Peoples R China RMIT Melbourne Vic Australia Chinese Univ Geosci Wuhan Peoples R China Newcastle Univ Sch Comp Sci Newcastle Upon Tyne Tyne & Wear England

During the last decade, cloud-technology has presented considerable opportunities for high-performance computing (HPC). In addition, technical computing data centers have been able to maximize their return on investment (ROI). HPC system managers can leverage the benefits of a cloud model for their traditional HPC environments to improve scalability, simplify service access, accelerate collaboration or funding, enable pay-for-use, and improve efficiency. Many HPC clouds assume the form of private Infrastructure as a Service (IaaS). In practice, private cloud users may strategically misreport task values in order to achieve a high profit, and thus cloud providers cannot simply maximize the sum of allocatedusers' value, which is called social welfare. For this reason, designing a mechanism that reveals the truthful value of users with a concern for both random arrival tasks and maximizing social welfare is necessary. In this study, a model of an online mechanism for virtual machines allocation is built, a preemptive online mechanism is proposed, the truthfulness is proved, a competitive ratio is given, and several simulations are conducted using real tasks from a data center. The total values and completed tasks are compared to the online and offline allocations, respectively, according to different capacity. The simulations reveal that our mechanism is more efficient than the offline mechanism. (C) 2016 Published by Elsevier B.V.

关键词： Cloud computing Preemptive allocation online algorithm Truthfulness Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online Allocation of Communication and Computation Resources for Real-Time Multimedia Services

引用

IEEE TRANSACTIONS ON MULTIMEDIA 2013年第3期15卷 670-683页

作者： Liao, Jun Chou, Philip A. Yuan, Chun Hu, Yusuo Zhu, Wenwu China Mobile Commun Corp Informat Secur Ctr Beijing 100053 Peoples R China Microsoft Res Redmond WA 98052 USA Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China Google Mountain View CA 94043 USA

In a network, the location of the node on which a service is computed is inextricably linked to the locations of the paths through which the service communicates. Hence, service location can have a profound effect on quality of service, especially for communication-centric applications such as real-time multimedia. In this paper, we propose an online algorithm that uses pricing to consider server load, route congestion, and propagation delay jointly when locating servers and routes for real-time multimedia services in a network with fixed computing and communication capacities. The algorithm is online in the sense that it is able to sequentially allocate resources for services with long and unknown duration as demands arrive, without the benefit of looking ahead to later demands. By formulating the problem as one of lowest cost subgraph packing, we prove that our algorithm is nevertheless C-competitive with the optimal algorithm that looks ahead, meaning that our performance is within a constant factor C of optimal, as measured by the total number of service demands satisfied, or total user utility. Using mixing services as an example, we show through experimental results that our algorithm can adapt to cross traffic and automatically route around congestion and failure of nodes and edges, can reduce latency by 40% or more, and can pack 20% more sessions or alternatively can double the number of sessions before significant call rejection, compared with conventional approaches.

关键词： Approximation algorithm congestion pricing mixing multimedia services online algorithm primal-dual algorithm resource allocation subgraph packing

来源：评论

学校读者我要写书评

暂无评论

online packet scheduling with bounded delay and lookahead

引用

THEORETICAL COMPUTER SCIENCE 2019年 776卷 95-113页

作者： Boehm, Martin Chrobak, Marek Jez, Lukasz Li, Fei Sgall, Jiri Vesely, Pavel Charles Univ Prague Comp Sci Inst Prague Czech Republic Univ Bremen Bremen Germany Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA Univ Wroclaw Inst Comp Sci Wroclaw Poland George Mason Univ Dept Comp Sci Fairfax VA 22030 USA Univ Warwick Dept Comp Sci Coventry W Midlands England

We study the online bounded delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature;yet currently the best published upper bound is 1.828 [8], still quite far from the best lower bound of phi approximate to 1.618 [11,2,6]. In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of phi applies even to the special case of 2-bounded instances, and a phi-competitive algorithm for 3-bounded instances was given in [5]. Improving that result, and addressing a question posed by Goldwasser [9], we present a phi-competitive algorithm for 4 bounded instances. We also study a variant of PacketScheduling where an online algorithm has the additional power of 1- lookahead, knowing at time t which packets will arrive at time t + 1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio 1/2 (root 13-1) approximate to 1.303 and we prove a nearly tight lower bound of 1/4 (1 + root 17) approximate to 1.281. In fact, our lower bound result is more general: using only 2-bounded instances, for any integer l >= 0 we prove a lower bound of 1/2(l+1) (1+root 5+8l+4l(2)) for online algorithms with l-lookahead, i.e., algorithms that at time t can see all packets arriving by time t + l. Finally, for non-restricted instances we show a lower bound of 1.25 for randomized algorithms with l-lookahead, for any l >= 0. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Buffer management online scheduling online algorithm Lookahead

来源：评论

学校读者我要写书评

暂无评论

Truthful online double auctions for on-demand integrated ride-sourcing platforms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第3期317卷 737-747页

作者： Ding, Xiaoshu Qi, Qi Jian, Sisi Hong Kong Univ Sci & Technol Dept Civil & Environm Engn Kowloon Clear Water Bay Hong Kong Peoples R China Renmin Univ China Gaoling Sch Artificial Intelligence Beijing Peoples R China

Integrated platforms are an emerging model of business that integrates ride-sourcing services provided by multiple companies on a single platform. It reduces market fragmentation and brings benefits to both travelers and participating independent transport service providers. To ensure the sustainability of such platforms, the main challenge lies in efficient matching between travelers and ride-sourcing companies, so that both sides obtain non-negative utility. In this study, we propose a double auction based framework to solve the matching and pricing problems for on-demand integrated ride-sourcing platforms. To solve the real-time matching problem, we develop two online mechanisms with a critical price dynamic updating algorithm and a greedy algorithm. The proposed mechanisms are guaranteed to achieve the desired economic properties, and their efficiency is evaluated through numerical studies.

关键词： Auction/bidding Demand responsive transport Integrated ride-sourcing platform Supply-demand matching online algorithm

来源：评论

学校读者我要写书评

暂无评论

Image Alignment by online Robust PCA via Stochastic Gradient Descent

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY 2016年第7期26卷 1241-1250页

作者： Song, Wenjie Zhu, Jianke Li, Yang Chen, Chun Zhejiang Univ Coll Comp Sci Hangzhou 310027 Peoples R China

Aligning a given set of images is usually conducted in batch mode manner, which not only requires large amount of memory but also adjusts all the previous transformations to register an input image. To address this issue, we propose a novel approach to image alignment by incorporating the geometric transformation into online robust principal component analysis (PCA). Instead of calculating the warp update using noisy input samples like the conventional methods, we suggest directly linearizing the object function by performing warp update on the recovered samples, which corresponds to an efficient inverse composition algorithm. Since the basis matrix is kept constant for a given sample, both the latent vector and warp update can be very efficiently computed. Moreover, we present two basis updating methods for robust PCA, including the closed-form solution and stochastic gradient descent scheme. We have conducted the extensive experiments on the real-world tasks of background subtraction with camera motion and visual tracking on the challenging video sequences, whose promising results demonstrate the efficacy of our presented approach.

关键词： Image alignment online algorithm robust principal component analysis (PCA)

来源：评论

学校读者我要写书评

暂无评论

online Incentive Mechanism Designs for Asynchronous Federated Learning in Edge Computing

引用

IEEE INTERNET OF THINGS JOURNAL 2024年第5期11卷 7787-7804页

作者： Li, Gang Cai, Jun He, Chengwen Zhang, Xiao Chen, Hongming Wuhan Textile Univ Sch Elect & Elect Engn Wuhan 430200 Peoples R China Concordia Univ Dept Elect & Comp Engn Network Intelligence & Innovat Lab Montreal PQ H4B 1R6 Canada Hunan Univ Technol & Business Sch Comp Sci Changsha 410205 Peoples R China South Cent Univ Nationalities Coll Comp Sci Wuhan 430074 Peoples R China Zhejiang Ocean Univ Key Lab Oceanog Big Data Min & Applicat Zhejiang Zhoushan 316022 Peoples R China Nankai Univ Coll Elect Informat & Opt Engn Tianjin 300350 Peoples R China

In this article, we consider incentive mechanism designs in asynchronous federated learning (FL) systems. With the consideration of unique characteristics inherent in asynchronous FL, such as dynamic participating and multiminded IoT nodes such as mobile users (MUs), requirements of model training (i.e., training accuracy and convergence time), and limited uplink bandwidth, we formulate considered system as an online incentive mechanism design problem, where each MU is not only a buyer for communication resource but also a seller for computation service. To address the challenges involved in the design, we first derive the relationship between the number of participants and the global training accuracy in asynchronous FL. Then, based on that, we propose a novel mechanism, called the online incentive mechanism for asynchronous FL (OIMAF). To the best of our knowledge, this is the first work to design incentive mechanisms for asynchronous FL. Furthermore, in order to obtain a more robust mechanism, an improved online mechanism, called the two-shot-based online incentive mechanism (TOIM), is proposed by using OIMAF as a building block. Theoretical analyses show that our proposed online incentive mechanisms can guarantee individual rationality, truthfulness, a sound performance, and solution feasibilities. We further conduct comprehensive simulations to validate the effectiveness of our proposed mechanisms.

关键词： Asynchronous federated learning (FL) competitive ratio (CR) edge computing incentive mechanism online algorithm

来源：评论

学校读者我要写书评

暂无评论

online scheduling of malleable parallel jobs with setup times on two identical machines

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第3期206卷 555-561页

作者： Guo, Shouwei Kang, Liying Shanghai Univ Dept Math Shanghai 200444 Peoples R China

In this paper we consider online scheduling of malleable parallel jobs on two identical machines, where jobs arrive over time. Each job J(j) has an execution time t(j) = p(j)/k(j) + (k(j) - 1)c(j) when it is processed on k(j) machines, where p(j) > 0 and c(j) > 0 are the length and setup time of job J(j). The objective is to minimize the makespan. For the problem with two machines, we present an online algorithm with competitive ratio of 1 + alpha, where alpha = (root 5 - 1)/2. We show that 1 + alpha is a lower bound on the competitive ratio of any online algorithm for the problem with m (m >= 2) machines. So our algorithm is optimal for the case of two machines. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Scheduling Parallel jobs Setup times online algorithm Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

online log parsing using evolving research tree

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2024年第2期66卷 1231-1255页

作者： Vervaet, Arthur Callau-Zori, Mar Chabchoub, Yousra Chiky, Raja 3DS OUTSCALE F-92210 St Cloud France ISEP Inst Super Elect Paris F-92130 Issy Les Moulineaux France

Logs are a reliable source of information for development and maintenance purposes. They record information at runtime regarding the state of a system and are commonly used to analyze its behavior. Parsing operations on logs structure the information embedded within the log message and are a crucial step for many log mining applications. In such use cases, parsing effectiveness can impact performance. For systems that require real-time performance, parsing efficiency is also an important factor. In this paper, we present USTEP, an online log parser that uses an evolving tree structure to encode and discover new parsing rules on the fly. Our evaluation of 14 datasets from different logging environments highlights the superiority of our method in terms of robustness and effectiveness compared to the state of the art. Our analysis of space and time complexity shows that USTEP is the only considered method capable of processing logs in constant time regardless of their length. We also propose here USTEP-UP, a way of running multiple USTEP instances in parallel.

关键词： Log parsing online algorithm Distributed algorithm Log mining

来源：评论

学校读者我要写书评

暂无评论

Improved lower bounds for the online bin packing problem with cardinality constraints

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第1期29卷 67-87页

作者： Fujiwara, Hiroshi Kobayashi, Koji Toyohashi Univ Technol Dept Comp Sci & Engn Toyohashi Aichi 4418580 Japan Natl Inst Informat Principles Informat Res Div Chiyoda Ku Tokyo 1018430 Japan

The bin packing problem has been extensively studied and numerous variants have been considered. The k-item bin packing problem is one of the variants introduced by Krause et al. (J ACM 22:522-550, 1975). In addition to the formulation of the classical bin packing problem, this problem imposes a cardinality constraint that the number of items packed into each bin must be at most k. For the online setting of this problem, in which the items are given one by one, Babel et al. (Discret Appl Math 143: 238-251, 2004) provided lower boundsv root 2 approximate to 1.41421 and 1.5 on the asymptotic competitive ratio for k = 2 and 3, respectively. For k >= 4, some lower bounds (e.g., by van Vliet (Inf Process Lett 43:277-284, 1992) for the online bin packing problem, i.e., a problem without cardinality constraints, can be applied to this problem. In this paper we consider the online k-item bin packing problem. First, we improve the previous lower bound 1.41421 to 1.42764 for k = 2. Moreover, we propose a new method to derive lower bounds for general k and present improved bounds for various cases of k >= 4. For example, we improve 1.33333 to 1.5 for k = 4, and 1.33333 to 1.47058 for k = 5.

关键词： Bin packing problem online algorithm Competitive analysis Cardinality constraint

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：