3 papers
cs.DS2026
A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
Kuowen Chen, Nicole Wein, Yiran Zhang
Given a graph and a pair of terminals , , the next-to-shortest path problem asks for an (simple) path that is shortest among all not shortest paths…
cs.DS2025
Adaptivity Gaps for Stochastic Probing with Subadditive Functions
Jian Li, Yinchen Liu, Yiran Zhang
In this paper, we study the stochastic probing problem under a general monotone norm objective. Given a ground set , each element has an independent nonnegative…
cs.DS2025
New Results on a General Class of Minimum Norm Optimization Problems
Kuowen Chen, Jian Li, Yuval Rabani +1
We study the general norm optimization for combinatorial problems, initiated by Chakrabarty and Swamy (STOC 2019). We propose a general formulation that captures a large class of c…