惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
Apple Machine Learning Research
Apple Machine Learning Research
T
Tailwind CSS Blog
月光博客
月光博客
爱范儿
爱范儿
有赞技术团队
有赞技术团队
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
aimingoo的专栏
aimingoo的专栏
GbyAI
GbyAI
腾讯CDC
The Cloudflare Blog
人人都是产品经理
人人都是产品经理
MongoDB | Blog
MongoDB | Blog
Microsoft Azure Blog
Microsoft Azure Blog
IT之家
IT之家
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
云风的 BLOG
云风的 BLOG
U
Unit 42
博客园 - 三生石上(FineUI控件)
A
About on SuperTechFans
N
Netflix TechBlog - Medium
Google DeepMind News
Google DeepMind News
雷峰网
雷峰网
L
LangChain Blog

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
Online Ride-Hitching in UAV Travelling
Songhua Li, Minming Li, Lingjie Duan, Victor C. S. Lee · 2021-08-22 · via cs.DS updates on arXiv.org

The unmanned aerial vehicle (UAV) has emerged as a promising solution to provide delivery and other mobile services to customers rapidly, yet it drains its stored energy quickly when travelling on the way and (even if solar-powered) it takes time for charging power on the way before reaching the destination. To address this issue, existing works focus more on UAV's path planning with designated system vehicles providing charging service. However, in some emergency cases and rural areas where system vehicles are not available, public trucks can provide more feasible and cost-saving services and hence a silver lining. In this paper, we explore how a single UAV can save flying distance by exploiting public trucks, to minimize the travel time of the UAV. We give the first theoretical work studying online algorithms for the problem, which guarantees a worst-case performance. We first consider the offline problem knowing future truck trip information far ahead of time. By delicately transforming the problem into a graph satisfying both time and power constraints, we present a shortest-path algorithm that outputs the optimal solution of the problem. Then, we proceed to the online setting where trucks appear in real-time and only inform the UAV of their trip information some certain time $Δt$ beforehand. As a benchmark, we propose a well-constructed lower bound that an online algorithm could achieve. We propose an online algorithm MyopicHitching that greedily takes truck trips and an improved algorithm $Δt$-Adaptive that further tolerates a waiting time in taking a ride. Our theoretical analysis shows that $Δt$-Adaptive is asymptotically optimal in the sense that its ratio approaches the proposed lower bounds as $Δt$ increases.