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

推荐订阅源

J
Java Code Geeks
S
SegmentFault 最新的问题
V
Visual Studio Blog
人人都是产品经理
人人都是产品经理
阮一峰的网络日志
阮一峰的网络日志
腾讯CDC
Stack Overflow Blog
Stack Overflow Blog
博客园 - 【当耐特】
Recent Announcements
Recent Announcements
I
InfoQ
U
Unit 42
博客园_首页
GbyAI
GbyAI
Hugging Face - Blog
Hugging Face - Blog
罗磊的独立博客
博客园 - 叶小钗
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
D
DataBreaches.Net
aimingoo的专栏
aimingoo的专栏
月光博客
月光博客
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
博客园 - 聂微东
T
Tailwind CSS 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
Controlling tail risk in two-slope ski rental
Qiming Cui, Michael Dinitz · 2025-08-09 · via cs.DS updates on arXiv.org

We study the optimal solution to a general two-slope ski rental problem with a tail risk, i.e., the chance of the competitive ratio exceeding a value $γ$ is bounded by $δ$. This extends the recent study of tail bounds for ski rental by [Dinitz et al. SODA 2024] to the two-slope version defined by [Lotker et al. IPL 2008]. In this version, even after "buying" we must still pay a rental cost at each time step, though it is lower after buying. This models many real-world "rent-or-buy" scenarios where a one-time investment decreases (but does not eliminate) the per-time cost. Despite this being a simple extension of the classical problem, we find that adding tail risk bounds creates a fundamentally different solution structure. For example, in our setting there is a possibility that we never buy in an optimal solution (which can also occur without tail bounds), but more strangely (and unlike the case without tail bounds or the classical case with tail bounds) we also show that the optimal solution might need to have nontrivial probabilities of buying even at finite points beyond the time corresponding to the buying cost. Moreover, in many regimes there does not exist a unique optimal solution. As our first contribution, we develop a series of structure theorems to characterize some features of optimal solutions. The complex structure of optimal solutions makes it more difficult to develop an algorithm to compute such a solution. As our second contribution, we utilize our structure theorems to design two algorithms: one based on a greedy algorithm combined with binary search that is fast but yields arbitrarily close to optimal solutions, and a slower algorithm based on linear programming which computes exact optimal solutions.