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

online algorithms for scheduling with machine activation cost

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2007年第2期24卷 263-277页

作者： He, Yong Han, Shuguang Jiang, Yiwei Zhejiang Sci Tech Univ Fac Sci Hangzhou 310018 Peoples R China Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China

In this paper, we consider a variant of the classical parallel machine scheduling problem. For this problem, we are given m potential identical machines to non-preemptively process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated, and when a job is revealed the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and activation cost of machines. We first present two optimal online algorithms with competitive ratios of 3/2 and 5/3 for m = 2, 3 cases, respectively. Then we present an online algorithm with a competitive ratio of at most 2 for general m >= 4, while the lower bound is 1.88.

关键词： parallel machine scheduling machine activation cost online algorithm competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Worst-case analysis of the FFH algorithm for online variable-sized bin packing

引用

COMPUTING 1996年第2期56卷 165-172页

作者： Zhang, G Institute of Applied Mathematics Academia Sinica Beijing People's Republic of China

We investigate and analyze the FFH algorithm proposed by Kinnersley and Langston [5]. We prove that the tight worst-case performance bound of FFH algorithm is 1.7, thereby answering a question in [5]. The case that bi... 详细信息

关键词： combinatorial problems bin packing online algorithm worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

An online Tilt Estimation and Compensation algorithm for a Small Satellite Camera

引用

INTERNATIONAL JOURNAL OF AERONAUTICAL AND SPACE SCIENCES 2018年第1期19卷 172-182页

作者： Lee, Da-Hyun Hwang, Jai-hyuk Def Agcy Technol & Qual Precedent Study Planning Team IT Venture Town Complex 5F35Techno 9 Ro Daejeon 52851 South Korea Korea Aerosp Univ Dept Aerosp & Mech Engn 76 Hanggongdaehak Ro Goyang Si 10540 Gyeonggi Do South Korea

In the case of a satellite camera designed to execute an Earth observation mission, even after a pre-launch precision alignment process has been carried out, misalignment will occur due to external factors during the launch and in the operating environment. In particular, for high-resolution satellite cameras, which require submicron accuracy for alignment between optical components, misalignment is a major cause of image quality degradation. To compensate for this, most high-resolution satellite cameras undergo a precise realignment process called refocusing before and during the operation process. However, conventional Earth observation satellites only execute refocusing upon de-space. Thus, in this paper, an online tilt estimation and compensation algorithm that can be utilized after de-space correction is executed. Although the sensitivity of the optical performance degradation due to the misalignment is highest in de-space, the MTF can be additionally increased by correcting tilt after refocusing. The algorithm proposed in this research can be used to estimate the amount of tilt that occurs by taking star images, and it can also be used to carry out automatic tilt corrections by employing a compensation mechanism that gives angular motion to the secondary mirror. Crucially, this algorithm is developed using an online processing system so that it can operate without communication with the ground.

关键词： Tilt algorithm online algorithm Small satellite camera Refocusing

来源：评论

学校读者我要写书评

暂无评论

algorithm for online 3-Path Vertex Cover

引用

THEORY OF COMPUTING SYSTEMS 2020年第2期64卷 327-338页

作者： Zhang, Yubai Zhang, Zhao Shi, Yishuo Li, Xianyue East China Univ Sci & Technol Coll Math Shanghai 200237 Peoples R China Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China Acad Sinica Inst Informat Sci Taibei 11529 Taiwan Lanzhou Univ Sch Math & Stat Lanzhou 730000 Gansu Peoples R China

A vertex set C of a graph G = (V, E) is a 3-path vertex cover if every path on 3 vertices has at least one vertex in C. This paper studies the online version of the minimum 3-path vertex cover problem, in which vertices are revealed one by one, and one has to determine whether the newly revealed vertex should be chosen into the solution without knowing future information. We show that a natural algorithm has competitive ratio at most Delta, where Delta is the maximum degree of the graph. An example is given showing that the ratio is tight.

关键词： online algorithm 3-path vertex cover

来源：评论

学校读者我要写书评

暂无评论

online Coordinated Charging Decision algorithm for Electric Vehicles Without Future Information

引用

IEEE TRANSACTIONS ON SMART GRID 2014年第6期5卷 2810-2824页

作者： Tang, Wanrong Bi, Suzhi Zhang, Ying Jun (Angela) Chinese Univ Hong Kong Dept Informat Engn Hong Kong Hong Kong Peoples R China Natl Univ Singapore Dept Elect & Comp Engn Singapore 117583 Singapore Chinese Univ Hong Kong Shenzhen Res Inst Shenzhen 999077 Peoples R China

The large-scale integration of plug-in electric vehicles (PEVs) to the power grid spurs the need for efficient charging coordination mechanisms. It can be shown that the optimal charging schedule smooths out the energy consumption over time so as to minimize the total energy cost. In practice, however, it is hard to smooth out the energy consumption perfectly, because the future PEV charging demand is unknown at the moment when the charging rate of an existing PEV needs to be determined. In this paper, we propose an online coordinated charging decision ( ORCHARD) algorithm, which minimizes the energy cost without knowing the future information. Through rigorous proof, we show that ORCHARD is strictly feasible in the sense that it guarantees to fulfill all charging demands before due time. Meanwhile, it achieves the best known competitive ratio of 2.39. By exploiting the problem structure, we propose a novel reduced-complexity algorithm to replace the standard convex optimization techniques used in ORCHARD. Through extensive simulations, we show that the average performance gap between ORCHARD and the offline optimal solution, which utilizes the complete future information, is as small as 6.5%. By setting a proper speeding factor, the average performance gap can be further reduced to 5%.

关键词： Competitive ratio online algorithm optimal charging control plug-in electrical vehicle smart grid worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

An energy-aware online task mapping algorithm in NoC-based system

引用

JOURNAL OF SUPERCOMPUTING 2013年第3期64卷 1021-1037页

作者： Xie, Bin Chen, Tianzhou Hu, Wei Tang, Xingsheng Wang, Dazhou Zhejiang Univ Coll Comp Sci Hangzhou 310027 Zhejiang Peoples R China Wuhan Univ Sci & Technol Coll Comp Sci & Technol Wuhan 430065 Peoples R China

With the development of the semiconductor technology, more processors can be integrated onto a single chip. Network-on-Chip is an efficient communication solution for many-core system. However, enhancing performance with lower energy consumption is still a challenge. One critical issue is mapping applications to NoC. This work proposed an online mapping method, which optimizes task mapping algorithm to reduce communication energy consumption. The communication status of applications at runtime is analyzed first. Then, the algorithm computes the mapping placement dynamically and implements the real-time mapping online. Experimental results based on simulation show that the algorithm proposed in this article can achieve more than 20% communication energy saving compared with first fit mapping and nearest neighbor mapping. The migration cost caused by the remapping process is also considered, and can be calculated at the runtime to estimate the effect of remapping.

关键词： Network-on-chip Energy consumption Mapping algorithm online algorithm Migration

来源：评论

学校读者我要写书评

暂无评论

An Optimal online Semi-Connected PLA algorithm With Maximum Error Bound

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2022年第1期34卷 164-177页

作者： Zhao, Huanyu Pang, Chaoyi Kotagiri, Ramamohanarao Pang, Christopher K. Deng, Ke Yang, Jian Li, Tongliang Zhejiang Univ NIT Sch Comp & Data Engn Shijiazhuang Hebei Peoples R China Zhejiang Univ Ningbo Inst Shijiazhuang Hebei Peoples R China Hebei Acad Sci Inst Appl Math Shijiazhuang Hebei Peoples R China Hebei Authenticat Technol Engn Res Ctr Shijiazhuang Hebei Peoples R China Univ Melbourne Parkville Vic 3010 Australia Univ Queensland Brisbane Qld 4072 Australia RMIT Univ Melbourne Vic 3000 Australia Macquarie Univ Sydney NSW 2109 Australia

Piecewise Linear Approximation (PLA) is one of the most widely used approaches for representing a time series with a set of approximated line segments. With this compressed form of representation, many large complicated time series can be efficiently stored, transmitted and analyzed. In this article, with the introduced concept of "semi-connection" that allowing two representation lines to be connected at a point between two consecutive time stamps, we propose a new optimal linear-time PLA algorithm SemiOptConnAlg for generating the least number of semi-connected line segments with guaranteed maximum error bound. With extended experimental tests, we demonstrate that the proposed algorithm is very efficient in execution time and achieves better performances than the state-of-art solutions.

关键词： Piecewise linear approximation (PLA) time series semi-connected bounded error in approximation online algorithm data stream

来源：评论

学校读者我要写书评

暂无评论

An online multi-agent co-operative learning algorithm in POMDPs

引用

JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE 2008年第4期20卷 335-344页

作者： Liu, Fei Zeng, Guangzhou Shandong Univ Sch Comp Sci & Technol Jinan 250100 Peoples R China

Solving partially observable Markov decision processes (POMDPs) is a complex task that is often intractable. This paper examines the problem of finding an optimal policy for POMDPs. While a lot of effort has been made to develop algorithms to solve POMDPs, the question of automatically finding good low-dimensional spaces in multi-agent co-operative learning domains has not been explored thoroughly. To identify this question, an online algorithm CMEAS is presented to improve the POMDP model. This algorithm is based on a look-ahead search to find the best action to execute at each cycle. Thus the overwhelming complexity of computing a policy for each possible situation is avoided. A series of simulations demonstrate this good strategy and performance of the proposed algorithm when multiple agents co-operate to find all optimal policy for POMDPs.

关键词： online algorithm multi-agent co-operative learning POMDPs

来源：评论

学校读者我要写书评

暂无评论

A Provably Efficient online Collaborative Caching algorithm for Multicell-Coordinated Systems

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2016年第8期15卷 1863-1876页

作者： Gharaibeh, Ammar Khreishah, Abdallah Ji, Bo Ayyash, Moussa New Jersey Inst Technol Dept Elect & Comp Engn Newark NJ 07102 USA Temple Univ Dept Comp & Informat Sci Philadelphia PA 19122 USA Chicago State Univ Dept Informat Studies Chicago IL 60628 USA

Caching at the base stations brings the contents closer to the users, reduces the traffic through the backhaul links, and reduces the delay experienced by the cellular users. The cellular network operator may charge the content providers for caching their contents. Moreover, content providers may lose their users if the users are not getting their desired quality of service, such as maximum tolerable delay in Video on Demand services. In this paper, we study the collaborative caching problem for a multicell-coordinated system from the point of view of minimizing the total cost paid by the content providers. We formulate the problem as an Integer Linear Program and prove its NP-completeness. We also provide an online caching algorithm that does not require any knowledge about the contents popularities. We prove that the online algorithm achieves a competitive ratio of O(log(n)), and we show that the best competitive ratio that any online algorithm can achieve is Omega(log(n)/loglog(n)). Therefore, our proposed caching algorithm is provably efficient. Through simulations, we show that our online algorithm performs very close to the optimal offline collaborative scheme, and can outperform it when contents popularities are not properly estimated.

关键词： Multicell-coordinated systems collaborative caching cellular networks online algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Covering and Packing Problems with Convex Objectives 57

Online Algorithms for Covering and Packing Problems with Con...

引用

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

作者： Azar, Yossi Buchbinder, Niv Chan, T-H. Hubert Chen, Shahar Cohen, Ilan Reuven Gupta, Anupam Huang, Zhiyi Kang, Ning Nagarajan, Viswanath Naor, Joseph (Seffi) Panigrahi, Debmalya Tel Aviv Univ Blavatnik Sch Comp Sci Tel Aviv Israel Tel Aviv Univ Dept Stat & Operat Res Tel Aviv Israel Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Technion Israel Inst Technol Dept Comp Sci Haifa Israel Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Univ Michigan Dept Ind & Operat Engn Ann Arbor MI 48109 USA Duke Univ Dept Comp Sci Durham NC 27708 USA

ISBN: (纸本)9781509039333

We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: min(x is an element of R+)(n) f(x) s.t. Ax >= 1, where f : R-+(n) -> R+ is a monotone convex function, and A is an m x n matrix with non-negative entries. In the online version, a new row of the constraint matrix, representing a new covering constraint, is revealed in each step and the algorithm is required to maintain a feasible and monotonically non-decreasing assignment x over time. We also consider a convex packing problem defined as: max(y is an element of R+)(m) Sigma(m)(j-1) y(j) - g(A(T) y), where g : R-+(n) -> R+ is a monotone convex function. In the online version, each variable y(j) arrives online and the algorithm must decide the value of y(j) on its arrival. This represents the Fenchel dual of the convex covering program, when g is the convex conjugate of f. We use a primal-dual approach to give online algorithms for these generic problems, and use them to simplify, unify, and improve upon previous results for several applications.

关键词： online algorithm convex optimization primal-dual algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：