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

online Double Auction for Wireless Spectrum Allocation With General Conflict Graph

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2022年第11期71卷 12222-12234页

作者： Cui, Yilun Yang, Lei Li, Ruidong Xu, Xiaohua Univ Sci & Technol China Dept Comp Sci Hefei 230026 Anhui Peoples R China South China Univ Technol Sch Software Engn Guangzhou 510640 Guangdong Peoples R China Kanazawa Univ Inst Sci & Engn Kanazawa Ishikawa 9201192 Japan

The spectrum usage often comes in an online fashion. Considering the selfish behaviors of both primary users(PUs) and sencond users(SUs), we design online double spectrum allocation methods. We propose a truthful online double auction for spectrum allocation. Preempting existing spectrum usage is not allowed. We design a strategyproof mechanism for both the primary user side and the SU side. In previous studies, users who do not interfere with each other have not been reasonably allocated to use channels. There is one and only one user on the used spectrum channel at a certain time, which will result in discarding many user requests. Our model allows multiple users to use a spectrum channel at the same time. Aiming at the shortcomings of previous research, we propose the concept of grouping for online auctions, so that all SUs that do not interfere with each other can use spectrum channels at the same time. This will greatly increase the number of users who use the spectrum at the same time. We thus increase the utilization rate of the user market, and a large number of users will not be idle and *** the design of our experiments, the grouping model proposed in this paper has obtained at least $43{\%}$ utilization rate on the set channel, and our experiments have obtained good generality for different interference radius.

关键词： Grouping model online algorithm online auction spectrum allocation

来源：评论

学校读者我要写书评

暂无评论

online economic ordering problem for deteriorating items with limited price information

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期44卷 2246-2268页

作者： Dai, Wenqiang Zheng, Meng Chen, Xu Yang, Zhuolin Univ Elect Sci & Technol China Sch Management & Econ Chengdu 611731 Sichuan Peoples R China

Traditional economic ordering model for deteriorating items assume the procurer have full information about the procurement price. In this paper, we study an online economic ordering problem for constant deteriorating rate items with limited price information under relative performance criterion of the competitive ratio (CR). We provide a simply procurement strategy as well as the optimal ordering quantity for each case. This procurement strategy is real-time and doesn't require any forecast, i.e., upon the arrival of price, the strategy concerning procurement time and quantity only be made based on arriving price and current inventory level, with entirely arbitrary non-stationary and even adversarial price sequence arrivals. A theoretical closed-form CR is also proven to give the performance guarantee. Our numerical experiments demonstrate even better empirical performance than the corresponding proven worst-case bounds.

关键词： online algorithm Deteriorating items Price Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

online mining maximal frequent structures in continuous landmark melody streams

引用

PATTERN RECOGNITION LETTERS 2005年第11期26卷 1658-1674页

作者： Li, HF Lee, SY Shan, MK Natl Chiao Tung Univ Dept Comp Sci & Informat Engn Hsinchu 300 Taiwan Natl Chengchi Univ Dept Comp Sci Taipei 116 Taiwan

In this paper, we address the problem of online mining maximal frequent structures (Type I & II melody structures) in unbounded, continuous landmark melody streams. An efficient algorithm, called MMSLMS (Maximal Melody Structures of Landmark Melody Streams), is developed for online incremental mining of maximal frequent melody substructures in one scan of the continuous melody streams. In MMSLMS, a space-efficient scheme, called CMB (Chord-set Memory Border), is proposed to constrain the upper-bound of space requirement of maximal frequent melody structures in such a streaming environment. Theoretical analysis and experimental study show that our algorithm is efficient and scalable for mining the set of all maximal melody structures in a landmark melody stream. (c) 2005 Elsevier B.V. All rights reserved.

关键词： machine learning data mining landmark melody stream maximal melody structure online algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimizing the Maximum Flow Time in the online Food Delivery Problem

引用

algorithmICA 2024年第4期86卷 907-943页

作者： Guo, Xiangyu Li, Shi Luo, Kelin Zhang, Yuhao Univ Buffalo Dept Comp Sci & Engn 105 White Rd Buffalo NY 14260 USA Univ Bonn Inst Comp Sci Poppelsdorfer Allee 49 D-53115 Bonn Germany Shanghai Jiao Tong Univ John Hopcroft Ctr Comp Sci 800 Dongchuan RD Shanghai 200240 Peoples R China Nanjing Univ Dept Comp Sci & Technol Nanjing Peoples R China

We study a common delivery problem encountered in nowadays online food-ordering platforms: Customers order dishes online, and the restaurant delivers the food after receiving the order. Specifically, we study a problem where k vehicles of capacity c are serving a set of requests ordering food from one restaurant. After a request arrives, it can be served by a vehicle moving from the restaurant to its delivery location. We are interested in serving all requests while minimizing the maximum flow-time, i.e., the maximum time length a customer waits to receive his/her food after submitting the order. The problem also has a close connection with the broadcast scheduling problem with maximum flow time objective. We show that the problem is hard in both offline and online settings even when k = 1 and c = infinity: There is a hardness of approximation of Omega(n) for the offline problem, and a lower bound of Omega(n) on the competitive ratio of any online algorithm, where n is number of points in the metric. We circumvent the strong negative results in two directions. Our main result is an O(1)-competitive online algorithm for the uncapaciated (i.e, c = infinity) food delivery problem on tree metrics;we also have a negative result showing that the condition c = infinity is needed. Then we consider the speed-augmentation model, in which our online algorithm is allowed to use alpha-speed vehicles, where alpha >= 1 is called the speeding factor. We develop an exponential time (1+ is an element of)-speeding 0 (1/ is an element of)-competitive algorithm for any is an element of >0. A polynomial time algorithm can be obtained with a speeding factor of alpha TSP+ is an element of or alpha(CVRP)+ is an element of, depending on whether the problem is uncapacitated. Here alpha(TSP) and alpha(CVRP) are the best approximation factors for the traveling salesman (TSP) and capacitated vehicle routing (CVRP) problems respectively. We complement the results with some negative ones.

关键词： online algorithm Capacitated vehicle routing Flow time optimization

来源：评论

学校读者我要写书评

暂无评论

online k-color spanning disk problems

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第2期46卷 1-14页

作者： Wang, Yin Xu, Yinfeng Zhang, Huili Tong, Weitian Xi An Jiao Tong Univ Sch Management State Key Lab Mfg Syst Engn Xian 710049 Peoples R China Georgia Southern Univ Dept Comp Sci Statesboro GA 30458 USA

Inspired by the applications in on-demand manufacturing, we introduce the online k-color spanning disk problem, the first online model for color spanning problems to the best of our knowledge. Given a set P of n colored points in a plane, with each color chosen from a set C of m <= n colors, the online k-color spanning disk problem determines the location of the center that minimizes the accumulated radius of theminimum spanning disks for a sequence of color sets, denoted by delta = < C-1, C-2,..., CT >, C-t subset of C, |C-t| >= k, t epsilon{1, 2,..., T}, as they are presented online. Here, a minimum spanning disk for a color set means a disk contains at least one point of each color. We construct a special instance to establish a lower bound on the performance of any online algorithms. Then, an O(nm log n)-time Voronoi-diagram-based algorithm is designed such that its competitive ratio matches the problem ' s lower bound. This implies our algorithm is theoretically the best possible in terms of the competitive ratio. We also introduce and study a variant, named the online balanced k-color spanning disk problem, for which a non-trivial lower bound and a best possible algorithm are presented.

关键词： Minimum color spanning disk Voronoi diagram online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Competitive Analysis of online Elastic Caching of Transient Data in Multi-Tiered Content Delivery Network

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2024年第12期35卷 2449-2462页

作者： Wu, Binghan Bao, Wei Zhou, Bing Bing Univ Sydney Sch Comp Sci Camperdown NSW 2006 Australia

As the demand for faster and more reliable content delivery escalates, Content Delivery Networks (CDNs) face significant challenges in managing content placement across their increasingly complex, multi-tiered structures to balance performance, complexity, and scalability, while addressing the transient nature of data and the unpredictability of internet traffic. Addressing these challenges, this study introduces a novel multi-tier CDN caching strategy that navigates spatial and temporal trade-offs in cache placement, considering the cache placement cost diminishes with the content lifetime, and the uncertainty of future data demands. We design a distributed online algorithm that evaluates each incoming request and places new caches when the total content delivery cost exceeds a threshold. Our competitive analysis shows a tight and optimal $\mathtt {Tiers}+1$Tiers+1 competitive ratio. Additionally, our algorithm has low complexity by passing $O(\mathtt {Tiers})$O(Tiers) number of reference messages for each request, which enhances its practical applicability. Empirical validation through numerical simulations and trace-driven experiments confirms the superiority of our approach to existing benchmarks in real-world CDN settings.

关键词： Content delivery networks (CDNs) content placement online algorithm competitive analysis Content delivery networks (CDNs) content placement online algorithm competitive analysis

来源：评论

学校读者我要写书评

暂无评论

online batch scheduling on parallel machines with delivery times

引用

THEORETICAL COMPUTER SCIENCE 2011年第39期412卷 5333-5339页

作者： Fang, Yang Lu, Xiwen Liu, Peihai E China Univ Sci & Technol Sch Sci Dept Math Shanghai 200237 Peoples R China

We study the online batch scheduling problem on parallel machines with delivery times. online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m = 2 or m = 3, respectively. When m >= 4, we present an online algorithm with a competitive ratio of 1.5 + o(1). (C) 2011 Elsevier B.V. All rights reserved.

关键词： online algorithm Batch scheduling Parallel machines Delivery time

来源：评论

学校读者我要写书评

暂无评论

Analysis of Lower Bounds for online Bin Packing with Two Item Sizes

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2021年第9期E104A卷 1127-1133页

作者： Fujiwara, Hiroshi Endo, Ken Yamamoto, Hiroaki Shinshu Univ Dept Elect & Comp Engn Nagano 3808553 Japan

In the bin packing problem, we are asked to place given items, each being of size between zero and one, into bins of capacity one. The goal is to minimize the number of bins that contain at least one item. An online algorithm for the bin packing problem decides where to place each item one by one when it arrives. The asymptotic approximation ratio of the bin packing problem is defined as the performance of an optimal online algorithm for the problem. That value indicates the intrinsic hardness of the bin packing problem. In this paper we study the bin packing problem in which every item is of either size alpha or size beta (<= alpha). While the asymptotic approximation ratio for alpha > 1/2 was already identified, that for alpha <= 1/2 is only partially known. This paper is the first to give a lower bound on the asymptotic approximation ratio for any alpha <= 1/2, by formulating linear optimization problems. Furthermore, we derive another lower bound in a closed form by constructing dual feasible solutions.

关键词： bin packing problem online algorithm competitive analysis mathematical optimization

来源：评论

学校读者我要写书评

暂无评论

online traveling salesman problem with time cost and non-zealous server

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第3期44卷 2143-2166页

作者： Wu, Tengyu He, Lin Yu, Haiyan Chongqing Univ Posts & Telecommun Chongqing Smart Post Engn Technol Res Ctr Sch Econ & Management Chongqing Peoples R China Chongqing Univ Posts & Telecommun Sch Econ & Management Chongqing Peoples R China Chongqing Jiaotong Univ Sch Econ & Management Inst Chongqing Port Logist & Shipping Chongqing Peoples R China

Considering that the time of meeting the demands is very important for emergency vehicle and emergency vehicle can't reject any request, we introduce a more realistic cost form into online traveling salesman problem(OL-TSP). When a new request arrives, if the salesman can't serve the request immediately, per-unit-time cost will be generated. The goal is to minimize server's total costs(travel makespan plus the per-unit-time costs). We consider the server is a non-zealous server and show that neither deterministic nor randomized online algorithms can achieve constant competitive ratio for OL-TSP on general metric space. While on truncated line segment and uniform metric space, we prove lower bounds, and present competitive online algorithms. Especially for the case with uniform metric space, we prove an optimal Greedy algorithm.

关键词： online algorithm Emergency vehicle routing Traveling salesman problem Per-unit-time cost

来源：评论

学校读者我要写书评

暂无评论

online Station Assignment for Electric Vehicle Battery Swapping

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2022年第4期23卷 3256-3267页

作者： You, Pengcheng Pang, John Z. F. Low, Steven H. Johns Hopkins Univ Dept Elect & Comp Engn Baltimore MD 21218 USA CALTECH Dept Comp & Math Sci Pasadena CA 91125 USA

This paper investigates the online station assignment for (commercial) electric vehicles (EVs) that request battery swapping from a central operator, i.e., in the absence of future information a battery swapping service station has to be assigned instantly to each EV upon its request. Based on EVs' locations, the availability of fully-charged batteries at service stations in the system, as well as traffic conditions, the assignment aims to minimize cost to EVs and congestion at service stations. Inspired by a polynomial-time offline solution via a bipartite matching approach, we develop an efficient and implementable online station assignment algorithm that provably achieves the tight (optimal) competitive ratio under mild conditions. Monte Carlo experiments on a real transportation network by Baidu Maps show that our algorithm performs reasonably well on realistic inputs, even with a certain amount of estimation error in parameters.

关键词： Electric vehicle battery swapping assignment bipartite matching online algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：