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

online algorithms for the maximum k-interval coverage problem

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第5期44卷 3364-3404页

作者： Li, Songhua Li, Minming Duan, Lingjie Lee, Victor C. S. City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Singapore Univ Technol & Design Engn Syst & Design Pillar Singapore Singapore Univ Hong Kong Dept Elect & Elect Engn Hong Kong Peoples R China

We study the online maximum coverage problem on a target interval, in which, given an online sequence of sub-intervals (which may intersect among each other) to arrive, we aim to select at most k of the sub-intervals such that the total covered length of the target interval is maximized. The decision to accept or reject each sub-interval is made immediately and irrevocably right at the release time of the sub-interval. We comprehensively study various settings of this problem regarding both the length of each released sub-interval and the total number of released sub-intervals. To begin with, we investigate the offline version of the problem where the sequence of all the released sub-intervals is known in advance to the decision-maker and propose two polynomial-time optimal solutions to different settings of our offline problem. For the online problem, lower bounds on the competitive ratio are first proposed on our well-designed release schemes of sub-intervals. Then, we propose a Single-threshOld-based deterministic algorithm (SOA), which adds a sub-interval if the added length without overlap exceeds a certain threshold, achieving competitive ratios close to the lower bounds. Further, we extend SOA to a Double-threshOlds-based deterministic algorithm (DOA) by using the first threshold for exploration and the second threshold (larger than the first one) for exploitation. With the two thresholds generated by our proposed program, we show that DOA outperforms SOA slightly in the worst-case scenario. Moreover, we show that more thresholds cannot induce better worst-case performance of an online deterministic algorithm as long as those thresholds are used in non-increasing order in accepting sub-intervals.

关键词： Maximum k-coverage problem online budgeted maximum coverage problem Interval coverage online algorithm

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Automotive Idling Reduction With Effective Statistics

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2015年第11期34卷 1742-1755页

作者： Dong, Chuansheng Zeng, Haibo Chen, Minghua McGill Univ Dept Elect & Comp Engn Montreal PQ H3A 0E9 Canada Virginia Tech Dept Elect & Comp Engn Blacksburg VA 24061 USA Chinese Univ Hong Kong Dept Informat Engn Hong Kong Hong Kong Peoples R China

Idling, or running the engine when the vehicle is not moving, accounts for 13%-23% of vehicle driving time and costs billions of gallons of fuel each year. In this paper, we consider the problem of idling reduction under the uncertainty of vehicle stop time. We abstract it as a classic ski rental problem, and propose a constrained version with two statistics mu(B)- and q(B+), the expected length of short stops and the probability of long stops. We develop two online algorithms, a suboptimal closed-form algorithm and an optimal numerical solution, that combine the best of the well-known deterministic and randomized schemes to minimize the worst case competitive ratio. We demonstrate the algorithms perform better than existing solutions in terms of both worst case guarantee and average case performance using simulation and real-world driving data.

关键词： Automotive idling reduction competitive analysis online algorithm ski rental problem

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Optimizing Age of Information in the IoT Systems with Multi-Slot Status Delivery

引用

IEEE WIRELESS COMMUNICATIONS LETTERS 2021年第5期10卷 971-975页

作者： Xie, Xin Wang, Heng Yu, Lei Weng, Mingjiang Chongqing Univ Posts & Telecommun Sch Commun & Informat Engn Chongqing 400065 Peoples R China Chongqing Univ Posts & Telecommun Key Lab Ind Internet Things & Networked Control Chongqing 400065 Peoples R China

Age of information (AoI) is recently proposed to measure the freshness of information, which provides a new performance metric for the real-time Internet of Things (IoT). In this letter, we investigate low complexity online algorithms to minimize the average AoI in an IoT system where the nodes are scheduled to sample the status with multiple packets and send it to the destination through noisy channels. Three online policies are proposed: Greedy policy, Max-Ratio policy and Lyapunov drift policy. Simulation results show that our online algorithms outperform the existing suboptimal algorithm and the Lyapunov drift policy yields the best performance.

关键词： Internet of Things Scheduling Noise measurement Time-varying channels Sensor systems Job shop scheduling Information age Sensor networks age of information Internet of Things scheduling online algorithm

来源：评论

学校读者我要写书评

暂无评论

d-connectivity of the random graph with restricted budget

引用

JOURNAL OF GRAPH THEORY 2025年第2期108卷 293-312页

作者： Lichev, Lyuben Univ Jean Monnet Inst Camille Jordan St Etienne France

In this short note, we consider a graph process recently introduced by Frieze, Krivelevich and Michaeli. In their model, the edges of the complete graph K-n are ordered uniformly at random and are then revealed consecutively to a player called Builder. At every round, Builder must decide if they accept the edge proposed at this round or not. We prove that, for every d >= 2, Builder can construct a spanning d-connected graph after (1 + o (1)) n log n/2 rounds by accepting (1 + o (1)) dn/2 edges with probability converging to 1 as n -> 8. This settles a conjecture of Frieze, Krivelevich and Michaeli.

关键词： connectivity online algorithm random graph random process restricted budget sharp threshold

来源：评论

学校读者我要写书评

暂无评论

online algorithms for the general k-search problem

引用

INFORMATION PROCESSING LETTERS 2011年第14期111卷 678-682页

作者： Zhang, Wenming Xu, Yinfeng Zheng, Feifeng Liu, Ming Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Peoples R China Tongji Univ Sch Econ & Management Shanghai 200092 Peoples R China

This paper investigates the general k-search problem, in which a player is to sell totally k units of some asset within n periods, aiming at maximizing the total revenue. At each period, the player observes a quoted price which expires before the next period, and decides irrecoverably the amount of the asset to be sold at the price. We present a deterministic online algorithm and prove it optimal for the case where k <= n - 1. For the other case where k >= n, we show by numerical illustration that the gap between the upper and the lower bound of competitive ratio is quite small for many situations. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Time series search One-way trading online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Deterministic primal-dual algorithms for online k-way matching with delays

引用

THEORETICAL COMPUTER SCIENCE 2025年 1026卷

作者： Kakimura, Naonori Nakayoshi, Tomohiro Keio Univ 3-14-1 HiyoshiKohoku Ku Minato Kanagawa 2238522 Japan Univ Tokyo 7-3-1 HongoBunkyo Ku Tokyo 1138654 Japan

In this paper, we study the Min-cost Perfect k-way Matching with Delays (k-MPMD), recently introduced by Melnyk et al. In the problem, m requests arrive one-by-one over time in a metric space. At any time, we can irrevocably make a group of k requests who arrived so far, that incurs the distance cost among the k requests in addition to the sum of the waiting cost for the k requests. The goal is to partition all the requests into groups of k requests, minimizing the total cost. The problem is a generalization of the min-cost perfect matching with delays (corresponding to 2- MPMD). It is known that no online algorithm for k-MPMD can achieve a bounded competitive ratio in general, where the competitive ratio is the worst-case ratio between its performance and the offline optimal value. On the other hand, k-MPMD is known to admit a randomized online algorithm with competitive ratio O(k5 log n) for a certain class of k-point metrics called the Hmetric, where n is the size of the metric space. In this paper, we propose a deterministic online algorithm with a competitive ratio of O(mk2) for the k-MPMD in H-metric space. Furthermore, we show that the competitive ratio can be improved to O(m + k2) if the metric is given as a diameter on a line.

关键词： online matching online algorithm Competitive analysis Delayed service

来源：评论

学校读者我要写书评

暂无评论

CPN meets learning: online scheduling for inference service in Computing Power Network

引用

COMPUTER NETWORKS 2025年 256卷

作者： Ji, Mingtao Qi, Ji Jiao, Lei Luo, Gangyi Zhao, Hehan Li, Xin Ye, Baoliu Qian, Zhuzhong Nanjing Univ Sch Comp Sci State Key Lab Novel Software Technol Nanjing 210023 Peoples R China China Mobile Suzhou Software Technol Co LTD Suzhou Jiangsu Peoples R China Univ Oregon Dept Comp Sci Eugene OR 97403 USA Nanjing Univ Aeronaut & Astronaut Nanjing 211106 Jiangsu Peoples R China

The advent of Computing Power Network (CPN) has opened up vast opportunities for machine learning inference, yet the challenge of reducing high operational cost due to intensive computations and the sheer volume of inference tasks cannot be overlooked. Scheduling inference tasks for mitigating operational cost involves various challenges, such as migrating tasks under unpredictable CPN status, making time-coupled decisions for resource provisioning, and selecting computing sites based on dynamic electricity prices. To address these issues, we introduce CPN-Inference, a novel and flexible inference framework built upon CPN. Specifically, we formulate a time-varying integer program problem that aims to minimize long-term cost, involving switching cost, operational cost, communication cost, queuing cost, and accuracy loss. We also propose a group of polynomial-time online algorithms for supporting the formulated problem by solving delicately constructed subproblems based on the inputs predicted via online learning. Furthermore, our algorithms are proven for their competitive ratio, showcasing the performance gap between our approach and the offline optimum. A testbed is constructed to evaluate inference performance on real devices. Our comprehensive evaluations, based on datasets from real systems, demonstrate that our algorithms outperform multiple alternatives, by achieving an average cost reduction of 35%.

关键词： Scheduling for Computing Power Network online Learning Resource Provisioning online algorithm

来源：评论

学校读者我要写书评

暂无评论

Caching or re-computing: online cost optimization for running big data tasks in IaaS clouds

引用

JOURNAL OF NETWORK AND COMPUTER APPLICATIONS 2025年 235卷

作者： Fu, Xiankun Pan, Li Liu, Shijun Shandong Univ Sch Software Jinan Peoples R China

High computing power and large storage capacity are necessary for running big data tasks, which leads to high infrastructure costs. Infrastructure-as-a-Service (IaaS) clouds can provide configuration environments and computing resources needed for running big data tasks, while saving users from expensive software and hardware infrastructure investments. Many studies show that the cost of computation can be reduced by caching intermediate results and reusing them instead of repeating computations. However, the storage cost incurred by caching a large number of intermediate results over along period of time may exceed the cost of computation, ultimately leading to an increase in total cost instead. For making optimal caching decisions, future usage profiles for big data tasks are needed, but it is generally very hard to predict them precisely. In this paper, to address this problem, we propose two practical online algorithms, one deterministic and the other randomized, which can determine whether to cache intermediate results to reduce the total cost of big data tasks without requiring any future information. We prove theoretically that the competitive ratio of the proposed deterministic (randomized) algorithm is min(2 - 1-eta, 2 - eta beta) (resp., e e-1 ). Using real-world Wikipedia data as well as synthetic datasets, we verify the effectiveness of our proposed algorithms through a large number of experiments based on the price of Alibaba's public IaaS cloud products.

关键词： Cloud computing Big data analysis online algorithm Competitive analysis Infrastructure-as-a-service cloud Cost optimization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：