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

algorithmS TO SOLVE UNBOUNDED CONVEX VECTOR OPTIMIZATION PROBLEMS

SIAM JOURNAL ON OPTIMIZATION 2023年第4期33卷 2598-2624页

作者： Wagner, Andrea Ulus, Firdevs Rudloff, Birgit Kovacova, Gabriela Hey, Niklas Vienna Univ Econ & Business Inst Stat & Math A-1020 Vienna Austria Bilkent Univ Dept Ind Engn TR-06800 Ankara Turkiye

This paper is concerned with solution algorithms for general convex vector optimization problems (CVOPs). So far, solution concepts and approximation algorithms for solving CVOPs exist only for bounded problems [C. Ararat, F. Ulus, and M. Umer, J. Optim. Theory Appl., 194 (2022), pp. 681-712], [D. Dorfler, A. Lohne, C. Schneider, and B. Wei ss ing, Optim. Methods Softw., 37 (2022), pp. 1006-1026], [A. Lohne, B. Rudloff, and F. Ulus, J. Global Optim., 60 (2014), pp. 713-736]. They provide a polyhedral inner and outer approximation of the upper image that have a Hausdorff distance of at most epsilon. However, it is well known (see [F. Ulus, J. Global Optim., 72 (2018), pp. 731-742]), that for some unbounded problems such polyhedral approximations do not exist. In this paper, we will propose a generalized solution concept, called an (epsilon, delta)-solution, that allows one to also consider unbounded CVOPs. It is based on additionally bounding the recession cones of the inner and outer polyhedral approximations of the upper image in a meaningful way. An algorithm is proposed that computes such delta-outer and delta-inner approximations of the recession cone of the upper image. In combination with the results of [A. L"ohne, B. Rudloff, and F. Ulus, J. Global Optim., 60 (2014), pp. 713-736] this provides a primal and a dual algorithm that allow one to compute (epsilon, delta)-solutions of (potentially unbounded) CVOPs. Numerical examples are provided.

关键词： convex vector optimization unbounded problems approximation algorithm approximation of cones

来源：评论

学校读者我要写书评

暂无评论

WEND: An Efficient WSN-Assisted Emergency Navigation algorithm for Dynamic Hazardous Ship Indoor Environments

引用

IEEE SENSORS JOURNAL 2023年第1期23卷 632-646页

作者： Liu, Kezhong Ma, Yuting Chen, Mozi Wang, Kehao Zheng, Kai Zeng, Xuming Wuhan Univ Technol Natl Engn Res Ctr Water Transport Safety Sch Nav Wuhan 430063 Peoples R China Wuhan Univ Technol Hubei Key Lab Inland Shipping Technol Wuhan 430063 Peoples R China Wuhan Univ Technol Sch Nav Wuhan 430063 Peoples R China Wuhan Univ Technol Sch Informat Engn Wuhan 430063 Peoples R China

A reliable and efficient emergency evacuation of a damaged cruise ship is essential for passenger safety. Although many advanced evacuation approaches based on wireless sensor networks (WSNs) are capable of exploring dynamic environmental hazards and provide real-time navigation service, such approaches are mainly used in buildings on land, taking no account of the complex ship structure, deadline for ship survival, and dynamic ship inclination, and therefore may fail to evacuate passengers before ship capsizing. This article proposes WEND, an efficient WSN-assisted emergency navigation algorithm for dynamic hazardous ship indoor environment, which informs each passenger about a hazard-avoid route that minimizes the total dynamic typical delay with error bound guarantee while meeting the deadline for ship capsizing in a real-time manner. To achieve this aim, WEND investigates ship interior layout to construct a 3-D topological model and analyzes the time-history of the roll motion of a damaged passenger ship to evaluate ship survival time and the dynamics of pedestrian movement. Then, an efficient adaptive emergency navigation algorithm building on the ideas of Hassin's algorithm is presented to provide a hazard-avoid path from each passenger's current location to boarding stations such that the worst-case delay along this path is no greater than the specified deadline, and the total dynamic typical delay is small. We evaluate our algorithm by conducting extensive simulations. The results demonstrate that WEND improves the navigation success ratio by approximately 30% and 10% compared with the state-of-the-art navigation methods, namely the expected number of oscillations (ENO)-based oscillation-free method (OPEN) and the deadline-aware adaptive emergency navigation strategy (ANT), respectively.

关键词： Marine vehicles Navigation Delays Heuristic algorithms Wireless sensor networks Sensors Legged locomotion approximation algorithm dynamic navigation model ship evacuation wireless sensor networks (WSNs)

来源：评论

学校读者我要写书评

暂无评论

Mobility-Aware Proactive Flow Setup in Software-Defined Mobile Edge Networks

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2023年第3期71卷 1549-1563页

作者： Zeng, Yue Ye, Baoliu Tang, Bin Lu, Sanglu Xu, Feng Guo, Song Qu, Zhihao Nanjing Univ Natl Key Lab Novel Software Technol Nanjing 210023 Peoples R China Hohai Univ Sch Comp & Informat Nanjing 211100 Peoples R China HongKong Polytech Univ Hong Kong Peoples R China

The software-defined network (SDN) enabled mobile edge network greatly facilitates network resource management and promotes many emerging applications. However, user mobility may cause the SDN controller to set flow rules frequently, introduce additional flow setup latency, cause delay jitter, and undermine latency-sensitive services. Proactive flow setup is an effective way to eliminate flow setup latency, but existing work fails to maximize the flow setup hit ratio, a metric for evaluating the quality of proactive flow setup decisions, which is critical for latency-sensitive services. In this paper, we study how to proactively set flow rules to maximize the flow setup hit ratio under limited available network resources to eliminate the flow setup latency as much as possible. Then, we formalize the proactive flow setup problem as two integer linear programming problems under two typical routing strategies, default routing and dynamic routing. Both problems are proved to be NP-hard. To tackle these two problems, we propose a linear programmingbased polynomial-time approximation algorithm for the default routing case and a greedy-based heuristic algorithm for the dynamic routing case. Extensive trace-driven experimental and simulation results verify that our algorithms can improve the flow setup hit ratio by up to 30.99% compared to existing solutions.

关键词： Software-defined networking mobile edge computing 5G approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Vehicle scheduling problems with two agents on a line

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-18页

作者： Yan, Hao Liu, Peihai Lu, Xiwen East China Univ Sci & Technol Shanghai Peoples R China

This paper studies the two-agent vehicle scheduling problems on a line with the constraint that each job is processed after its release time. All jobs belong to agent A or agent B and each job is located at some vertex on the line. The vehicle starts from an initial vertex vo to process all jobs. The objective of the problem is to find a route of the vehicle so as to minimize the makespan of agent A under the constraint condition that the makespan of agent B is no more than the threshold value Q. This problem can be expressed by the 3-field scheduling notations as line - l vertical bar r(v(j)), C-max(B) <= Q vertical bar C-max(A), For the problem without release time, we show this problem is solvable in polynomial time and an O(n) time algorithm is provided. For the problem with release time, we prove this problem is NP-hard and then, a 3+root 5/2-approximation algorithm is presented. Finally, we conclude the numerical experiments to evaluate the performance of the approximation algorithm.

关键词： Network scheduling Agent scheduling Polynomial time algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Covering Users With QoS by a Connected Swarm of Drones: Graph Theoretical Approach and Experiments

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2023年第6期31卷 2483-2498页

作者： Danilchenko, Kiril Nutov, Zeev Segal, Michael Ben Gurion Univ Negev Sch Elect & Comp Engn IL-84105 Beer Sheva Israel Open Univ Israel Comp Sci Dept IL-4353701 Raanana Israel

In this work, we study the connected version of the covering problem motivated by the coverage of ad-hoc drones' swarm. We focus on the situation where the number of drones is given, and this number is not necessarily enough to cover all users. That is, we deal with a budget optimization problem, where the budget is the number of given drones. We assume that each ground user has different QoS requirements. Additionally, each ground user has a weight that corresponds to the importance (rank) of the user. Moreover, we consider the case when there is no third-party entity that provides connectivity to the drones. In this paper, we propose a 3D deployment scheme with the given number of drones such that the sum of the weights (ranks) of the ground users covered by drones is maximized (when the covering radii satisfy QoS of these users), and the drones form a connected graph. We present a number of approximate solutions with provable guaranteed performance evaluation that have been validated also through the simulation platform.

关键词： Drones Quality of service Wireless communication Atmospheric modeling Signal to noise ratio approximation algorithms Three-dimensional displays Connected swarm of drones approximation algorithm coverage problem

来源：评论

学校读者我要写书评

暂无评论

A fast and deterministic algorithm for Knapsack-constrained monotone DR-submodular maximization over an integer lattice

引用

JOURNAL OF GLOBAL OPTIMIZATION 2023年第1期85卷 15-38页

作者： Gong, Suning Nong, Qingqin Bao, Shuyu Fang, Qizhi Du, Ding-Zhu Ocean Univ China Sch Math Sci Qingdao 266100 Shandong Peoples R China Univ Texas Dallas Dept Comp Sci Dallas TX 75083 USA

We consider a knapsack-constrained maximization problem of a nonnegative monotone DR-submodular function f over a bounded integer lattice [B] in R-+(n), max{f (x) : x is an element of [B] and Sigma(n)(i=1) x(i)c(i) <= 1}, where n is the cardinality of a ground set N and c(.) is a cost function defined on N. Soma and Yoshida [Math. Program., 172 (2018), pp. 539-563] present a (1 - e(-1) - O(epsilon))-approximation algorithm for this problem by combining threshold greedy algorithm with partial element enumeration technique. Although the approximation ratio is almost tight, their algorithm runs in O(n(3)/epsilon(3) log(3) tau[log(3) parallel to B parallel to(infinity) + n/epsilon log parallel to B parallel to(infinity) log 1/epsilon c(min)]) time, where c(min) = min(i) c(i) and tau is the /ratio of the maximum value of f to the minimum nonzero increase in the value of f . Besides, Ene and Nguyen [arXiv:1606.08362, 2016] indirectly give a (1 - e(-1) - O(epsilon))-approximation algorithm with O((1/epsilon)(O(1/epsilon 4))n log parallel to B parallel to(infinity) log(2) (n log parallel to B parallel to(infinity))) time. But their algorithm is random. In this paper, we make full use of the DR-submodularity over a bounded integer lattice, carry forward the greedy idea in the continuous process and provide a simple deterministic rounding method so as to obtain a feasible solution of the original problem without loss of objective value. We present a deterministic algorithm and theoretically reduce its running time to a new record, O((1/epsilon)(O(1 /epsilon 5)) . n log 1/c(min) log parallel to B parallel to(infinity)), with the same approximate ratio.

关键词： DR-submodular maximization Knapsack constraint Integer lattice approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Autonomous Recharging and Flight Mission Planning for Battery-Operated Autonomous Drones

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2023年第2期20卷 1034-1046页

作者： Alyassi, Rashid Khonji, Majid Karapetyan, Areg Chau, Sid Chi-Kin Elbassioni, Khaled Tseng, Chien-Ming Khalifa Univ Dept EECS Abu Dhabi U Arab Emirates Australian Natl Univ Coll Engn & Comp Sci Canberra ACT 2601 Australia Ubiquiti Inc Taipei 21088 Taiwan

Unmanned aerial vehicles (UAVs), commonly known as drones, are being increasingly deployed throughout the globe as a means to streamline monitoring, inspection, mapping, and logistic routines. When dispatched on autonomous missions, drones require an intelligent decision-making system for trajectory planning and tour optimization. Given the limited capacity of their onboard batteries, a key design challenge is to ensure the underlying algorithms can efficiently optimize the mission objectives along with recharging operations during long-haul flights. With this in view, the present work undertakes a comprehensive study on automated tour management systems for an energy-constrained drone: (1) We construct a machine learning model that estimates the energy expenditure of typical multi-rotor drones while accounting for real-world aspects and extrinsic meteorological factors. (2) Leveraging this model, the joint program of flight mission planning and recharging optimization is formulated as a multi-criteria Asymmetric Traveling Salesman Problem (ATSP), wherein a drone seeks for the time-optimal energy-feasible tour that visits all the target sites and refuels whenever necessary. (3) We devise an efficient approximation algorithm with provable worst-case performance guarantees and implement it in a drone management system, which supports real-time flight path tracking and re-computation in dynamic environments. (4) The effectiveness and practicality of the proposed approach are validated through extensive numerical simulations as well as real-world experiments.

关键词： Drones Batteries Routing Planning Power demand Charging stations approximation algorithms Unmanned aerial vehicles flight mission planning recharging optimization power consumption modeling approximation algorithm traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

Maximizing Sensor Lifetime via Multi-node Partial-Charging on Sensors

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2023年第11期22卷 6571-6584页

作者： Liu, Jingxiang Peng, Jian Xu, Wenzheng Liang, Weifa Liu, Tang Peng, Xi Xu, Zichuan Li, Zheng Jia, Xiaohua Sichuan Univ Coll Comp Sci Chengdu 610065 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Sichuan Normal Univ Coll Comp Sci Chengdu 610068 Peoples R China Dalian Univ Technol Sch Software Dalian 116024 Peoples R China

In this paper, we study the employment of a mobile charger to charge lifetime-critical sensors under the multi-node partial-charging model, in which the charger can simultaneously charge the sensors within its charging range and each sensor may be partially charged each time. We notice that existing studies only scheduled the charger to minimize the number of dead sensors, but did not consider the charging scheduling for the sensors that have already run out of their energy, and the dead sensors will be last charged by the mobile charger. Then, their dead durations may be very long. In this paper, we consider not only how to minimize the number of dead sensors but also reduce the dead durations of sensors. To this end, we first formulate a sensor lifetime maximization problem, which is to find a charging tour for a mobile charger to charge sensors, such that the sum of sensor lifetimes is maximized. We then propose a novel $\frac{1}{3}$13-approximation algorithm for the problem. We finally evaluate the performance of the proposed algorithm through experiments. Experimental results show that both the average and maximum sensor dead durations by the proposed algorithm are up to 70% shorter than those by existing algorithms.

关键词： Wireless sensor networks Schedules Energy consumption Wireless rechargeable sensor networks multi-node charging partial charging approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Joint Caching and Routing in Cache Networks With Arbitrary Topology

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2023年第8期34卷 2237-2250页

作者： Xie, Tian Thakkar, Sanchal He, Ting McDaniel, Patrick Burke, Quinn Penn State Univ University Pk PA 16802 USA Univ Wisconsin Madison Madison WI 53706 USA

In-network caching and flexible routing are two of the most celebrated advantages of next generation network infrastructures. Yet few solutions are available for jointly optimizing caching and routing that provide performance guarantees for networks with arbitrary topology. We take a holistic approach towards this fundamental problem by analyzing its complexity in all the cases and developing polynomial-time algorithms with approximation guarantees in important special cases. We also reveal the fundamental challenge in achieving guaranteed approximation in the general case and propose an alternating optimization algorithm with good empirical performance and fast convergence. Our algorithms have demonstrated superior performance in both routing cost and congestion compared to the state-of-the-art solutions in evaluations based on real topology and request traces.

关键词： approximation algorithm cache network joint caching and routing unsplittable flow problem

来源：评论

学校读者我要写书评

暂无评论

Extreme flow decomposition for multi-source multicast with intra-session network coding

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2023年第1期175卷 80-91页

作者： Zhang, Jianwei Yunnan Univ Sch Informat Sci & Engn Kunming Peoples R China

Network coding (NC), when combined with multipath routing, enables a linear programming (LP) formulation for a multi-source multicast with intra-session network coding (MISNC) problem. However, it is still hard to solve using conventional methods due to the enormous scale of variables or constraints. In this paper, we try to solve this problem in terms of throughput maximization from an algorithmic perspective. We propose a novel formulation based on the extreme flow decomposition technique, which facilitates the design and analysis of approximation and online algorithms. For the offline scenario, we develop a fully polynomial time approximation scheme (FPTAS) which can find a (1 +w) -approximation solution for any specified w > 0. For the online scenario, we develop an online primal-dual algorithm which proves O(1)-competitive and violates link capacities by a factor of O (log m), where m is the link number. The proposed algorithms share an elegant primal-dual form and thereby have inherent advantages of simplicity, efficiency, and scalability. To better understand the proposed approach, we devise delicate numerical examples on an extended butterfly network to validate the effects of algorithmic parameters and make an interesting comparison between the offline and online cases. We also perform large-scale simulations on real networks to validate the effectiveness of the proposed FPTAS and online algorithm. (c) 2023 Elsevier Inc. All rights reserved.

关键词： Network coding Multicast Extreme flow approximation algorithm Online algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：