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

auction algorithms for shortest hyperpath problems

SIAM JOURNAL ON OPTIMIZATION 2000年第1期11卷 149-159页

作者： De Leone, R Pretolani, D Univ Camerino Dipartimento Matemat & Fis I-62032 Camerino MC Italy

The auction-reduction algorithm is a strongly polynomial version of the auction method for the shortest path problem. In this paper we extend the auction-reduction algorithm to different types of shortest hyperpath problems in directed hypergraphs. The results of preliminary computational experiences show that the auction-reduction method is comparable to other known methods for specific classes of hypergraphs.

关键词： directed hypergraphs hyperpaths shortest paths auction algorithms

来源：评论

学校读者我要写书评

暂无评论

Blockchain-Based UAV-Assisted Mobile Edge Computing for Dual Game Resource Allocation

引用

APPLIED SCIENCES-BASEL 2025年第7期15卷 4048-4048页

作者： Pang, Shanchen Tang, Yu Zhai, Xue Tong, Siyuan Wan, Zhenghao China Univ Petr East China Qingdao Inst Software Coll Comp Sci & Technol Qingdao 266580 Peoples R China State Key Lab Chem Safety Qingdao 266580 Peoples R China Shandong Key Lab Intelligent Oil & Gas Ind Softwar Qingdao 266580 Peoples R China

Featured Application The results of this study can be applied to the optimization of resource allocation in drone-server collaborative computing. This method has been successfully used in a decentralized resource-trading framework in an edge computing environment, and has broad application potential in scenarios such as smart manufacturing, smart transportation, and the industrial Internet of Things. It provides theoretical support and practical guidance for efficient and secure resource *** UAV-assisted mobile edge computing combines the flexibility of UAVs with the computing power of MEC to provide low-latency, high-performance computing solutions for a wide range of application scenarios. However, due to the highly dynamic and heterogeneous nature of the UAV environment, the optimal allocation of resources and system reliability still face significant challenges. This paper proposes a two-stage optimization (DSO) algorithm for UAV-assisted MEC, combining Stackelberg game theory and auction mechanisms to optimize resource allocation among servers, UAVs, and users. The first stage uses a Stackelberg game to allocate resources between servers and UAVs, while the second stage employs an auction algorithm for UAV-user resource pricing. Blockchain smart contracts automate task management, ensuring transparency and reliability. The experimental results show that compared with the traditional single-stage optimization algorithm (SSO), the equal allocation algorithm (EAA) and the dynamic resource pricing algorithm (DRP), the DSO algorithm proposed in this paper has significant advantages by improving resource utilization by 7-10%, reducing task latency by 3-5%, and lowering energy consumption by 4-8%, making it highly effective for dynamic UAV environments.

关键词： drones blockchain Stackelberg games auction algorithms two-tier games

来源：评论

学校读者我要写书评

暂无评论

Dynamic pricing and scheduling in LEO satellite networks

引用

COMPUTER NETWORKS 2025年 262卷

作者： Li, Xianglong Mo, Kaiwei Li, Zongpeng Xu, Hong Wuhan Univ Sch Comp Sci Wuhan Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Hangdian Univ Sch Automat Hangzhou Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Peoples R China

The dynamic nature of Low Earth Orbit (LEO) satellite networks, characterized by high-speed movement, narrow coverage, uneven spatial distribution and multi-satellite coordination, presents unique challenges and opportunities for network resource allocation. Existing literature has not fully addressed all the practical implementation challenges in LEO satellite networks;the predefined LEO pricing system lacks flexibility and does not consider user utility. This work introduces an auction-based framework to dynamically price and schedule Internet services in LEO satellite networks, optimizing resource allocation among users. We model the NP-Hard LEO Internet service scheduling problem into an Integer Linear Programming (ILP), providing both primal and dual forms. Leveraging an auction mechanism design, our online algorithm OSAL efficiently distributes satellite network resources while maximizing social welfare by ensuring resources are allocated to users who value them most. We demonstrate that OSAL effectively addresses the complexities of node mobility and spatial coverage in LEO satellites, improving the availability and efficiency of Internet services in this rapidly evolving field.

关键词： auction algorithms Optimization LEO networks

来源：评论

学校读者我要写书评

暂无评论

Mobile association scheme based on auction algorithm in heterogeneous wireless networks

引用

AD HOC NETWORKS 2024年 157卷

作者： Zhao, Junhui Bao, Xuehan Bian, Hongyi Zhang, Qingmiao Wang, Dongming Fan, Lisheng East China Jiaotong Univ Sch Informat Engn Nanchang 330013 Peoples R China Beijing Jiaotong Univ Sch Elect & Informat Engn Beijing 100044 Peoples R China Southeast Univ Sch Informat Sci & Engn Nanjing 210096 Peoples R China Guangzhou Univ Sch Comp Sci & Networking Engn Guangzhou 510006 Peoples R China

With the rapid development of mobile communications, the dense deployment of small base stations (SBSs) in heterogeneous wireless networks (HW-Nets) has met the explosive growth in demand from terminals. However, due to the irregular deployment of SBSs, users frequently handover base stations in pursuit of high -quality services, which inevitably leads to load imbalance among SBSs. To alleviate load imbalance in HW-Nets and improve the efficiency of seamless handover, this paper proposes a distributed auction algorithm scheme based on dual active protocol stack (DAPS), which transforms the wireless access selection of terminals into the terminal -base station association process during movement to globally optimize network resource utilization. At the same time, this paper constructs a terminal -base station association graph and uses auction algorithms to solve the maximum weighted matching of the graph. The DAPS -based scheme can effectively avoid the problem of excessively long outage time caused by handovering outages. Simulation results show that compared with general distributed algorithms, the distributed auction algorithm based on DAPS can effectively balance the load of base stations and reduce the mobile outage latency by 59% .

关键词： Heterogeneous wireless networks (HW-Nets) Dual active protocol stack (DAPS) auction algorithms Mobile handover

来源：评论

学校读者我要写书评

暂无评论

auction-Based On-Demand P2P Min-Cost Media Streaming with Network Coding

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2009年第12期20卷 1816-1829页

作者： Chu, Xiaowen Zhao, Kaiyong Li, Zongpeng Mahanti, Anirban Hong Kong Baptist Univ Dept Comp Sci Kowloon Hong Kong Peoples R China Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada NICTA Sydney NSW Australia

Realizing on-demand media streaming in a Peer-to-Peer (P2P) fashion is more challenging than in the case of live media streaming, since only peers with close-by media play progresses may help each other in obtaining the media content. The situation is further complicated if we wish to pursue low aggregated link cost in the transmission. In this paper, we present a new algorithmic perspective toward on-demand P2P streaming protocol design. While previous approaches employ streaming trees or passive neighbor reconciliation for media content distribution, we instead coordinate the streaming session as an auction where each peer participates locally by bidding for and selling media flows encoded with network coding. We show that this auction approach is promising in achieving low-cost on-demand streaming in a scalable fashion. It is amenable to asynchronous, distributed, and lightweight implementations, and is flexible to provide support for random-seek and pause functionalities. Through extensive simulation studies, we verify the effectiveness and performance of the proposed auction approach, focusing on the optimality in overall streaming cost, the convergence speed, and the communication overhead.

关键词： Communication/networking and information technology computer systems organization. multicast Internet working design studies performance of systems media streaming overlay networks auction algorithms

来源：评论

学校读者我要写书评

暂无评论

auction dynamics: A volume constrained MBO scheme

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2018年 354卷 288-310页

作者： Jacob, Matt Merkurjev, Ekaterina Esedoglu, Selim [⁎]Corresponding author.

We show how auction algorithms, originally developed for the assignment problem, can be utilized in Merriman, Bence, and Osher's threshold dynamics scheme to simulate multi-phase motion by mean curvature in the presence of equality and inequality volume constraints on the individual phases. The resulting algorithms are highly efficient and robust, and can be used in simulations ranging from minimal partition problems in Euclidean space to semi-supervised machine learning via clustering on graphs. In the case of the latter application, numerous experimental results on benchmark machine learning datasets show that our approach exceeds the performance of current state-of-the-art methods, while requiring a fraction of the computation time. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Threshold dynamics Assignment problem auction algorithms Volume constrained curvature motion Minimal partitions Machine learning

来源：评论

学校读者我要写书评

暂无评论

AN auction ALGORITHM FOR THE MAX-FLOW PROBLEM

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1995年第1期87卷 69-101页

作者： BERTSEKAS, DP Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology Cambridge

We propose a new algorithm for the max-flow problem. It consists of a sequence of augmentations along paths constructed by an auction-like algorithm. These paths are not necessarily shortest, that is, they need not contain a minimum number of arcs. However, they can be found typically with much less computation than the shortest augmenting paths used by competing methods. Our algorithm outperforms these latter methods as well as state-of-the-art preflow-push algorithms by a very large margin in tests with standard randomly generated problems.

关键词： NETWORK OPTIMIZATION MAX-FLOW PROBLEMS auction algorithms PREFLOW-PUSH algorithms

来源：评论

学校读者我要写书评

暂无评论

Greedy Decentralized auction-based Task Allocation for Multi-Agent Systems

Greedy Decentralized Auction-based Task Allocation for Multi...

引用

Modeling, Estimation and Control Conference (MECC)

作者： Braquet, Martin Bakolas, Efstathios Univ Texas Austin Dept Aerosp Engn & Engn Mech Austin TX 78712 USA

We propose a decentralized auction-based algorithm for the solution of dynamic task allocation problems for spatially distributed multi-agent systems. In our approach, each member of the multi-agent team is assigned to at most one task from a set of spatially distributed tasks, while several agents can be allocated to the same task. The task assignment is dynamic since it is updated at discrete time stages (iterations) to account for the current states of the agents as the latter move towards the tasks assigned to them at the previous stage. Our proposed methods can find applications in problems of resource allocation by intelligent machines such as the delivery of packages by a fleet of unmanned or semi-autonomous aerial vehicles. In our approach, the task allocation accounts for both the cost incurred by the agents for the completion of their assigned tasks (e.g., energy or fuel consumption) and the rewards earned for their completion (which may reflect, for instance, the agents' satisfaction). We propose a Greedy Coalition auction Algorithm (GCAA) in which the agents possess bid vectors representing their best evaluations of the task utilities. The agents propose bids, deduce an allocation based on their bid vectors and update them after each iteration. The solution estimate of the proposed task allocation algorithm converges after a finite number of iterations which cannot exceed the number of agents. Finally, we use numerical simulations to illustrate the effectiveness of the proposed task allocation algorithm (in terms of performance and computation time) in several scenarios involving multiple agents and tasks distributed over a spatial 2D domain. Copyright (C) 2021 The Authors.

关键词： Multi-agent and Networked Systems auction algorithms Decentralized Systems Trajectory Planning

来源：评论

学校读者我要写书评

暂无评论

An Online auction Approach to UAV Scheduling and Trajectory Planning 59

An Online Auction Approach to UAV Scheduling and Trajectory ...

引用

59th Annual IEEE International Conference on Communications (IEEE ICC)

作者： Mo, Kaiwei Li, Xianglong Xue, Chun Jason Li, Zongpeng Xu, Hong City Univ Hong Kong Comp Sci Hong Kong Peoples R China Wuhan Univ Comp Sci Wuhan Peoples R China MBZUAI Comp Sci Abu Dhabi U Arab Emirates Tsinghua Univ Network Sci & Cyberspace Beijing Peoples R China Chinese Univ Hong Kong Comp Sci & Engn Hong Kong Peoples R China

ISBN: (纸本)9781728190549

In times when ground infrastructure can be disrupted by conflicts or natural events, the use of Unmanned Aerial Vehicle (UAV) trajectories for network services has become a crucial backup plan. Yet, many current methods don't fully optimize how UAVs are scheduled or allocate resources, resulting in less effective service. Our research aims to enhance social welfare by optimizing UAV scheduling and trajectory planning. To tackle this challenging problem, we first set up a non-convex linear programming issue and then restructure it into both its exponential and dual forms. We introduce a two-part solution. The A(OST) algorithm manages task bids and UAV resource allocation, considering factors like bid values, resources, and task needs. It ranks tasks based on the value they bring. Next, the A(dual) algorithm refines decisions on tasks and UAV planning by weighing task costs against benefits. Our analysis shows our method reaches a balance that boosts social welfare, ensuring the best task and resource decisions. Tests back up these claims, showing improvement in network service, and proving our method's practical value in maximizing social welfare during disruptions.

关键词： UAV scheduling online optimization auction algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel algorithms for the minimum cost flow problem

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1997年第3期95卷 501-530页

作者： Beraldi, P Guerriero, F Musmanno, R Univ Calabria Dipartimento Elettron Informat & Sistemist I-87036 Cosenza Italy

In this paper, we propose efficient parallel implementations of the auction/sequential shortest path and the epsilon-relaxation algorithms for solving the linear minimum cost flow problem. In the parallel auction algorithm, several augmenting paths can be found simultaneously, each of them starting from a different node with positive surplus. Convergence results of an asynchronous version of the algorithm are also given. For the epsilon-relaxation method, there exist already parallel versions implemented on CM-5 and CM-2;our implementation is the first on a shared memory multiprocessor. We have obtained significant speedup values for the algorithms considered;it turns out that our implementations are effective and efficient.

关键词： network optimization minimum cost flow problems auction algorithms parallel asynchronous algorithms shared memory multiprocessors

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：