3 papers
cs.DS2025
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
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…
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…