Author name cluster

Ruimin Zhang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

NeurIPS Conference 2024 Conference Paper

Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling

Wei Tang
Haifeng Xu
Ruimin Zhang
Derek Zhu

Prophet inequality concerns a basic optimal stopping problem and states that simple threshold stopping policies --- i. e. , accepting the first reward larger than a certain threshold --- can achieve tight $\frac{1}{2}$-approximation to the optimal prophet value. Motivated by its economic applications, this paper studies the robustness of this approximation to natural strategic manipulations in which each random reward is associated with a self-interested player who may selectively reveal his realized reward to the searcher in order to maximize his probability of being selected. We say a threshold policy is $\alpha$(-strategically)-robust if it (a) achieves the $\alpha$-approximation to the prophet value for strategic players; and (b) meanwhile remains a $\frac{1}{2}$-approximation in the standard non-strategic setting. Starting with a characterization of each player's optimal information revealing strategy, we demonstrate the intrinsic robustness of prophet inequalities to strategic reward signaling through the following results: (1) for arbitrary reward distributions, there is a threshold policy that is $\frac{1-\frac{1}{e}}{2}$-robust, and this ratio is tight; (2) for i. i. d. reward distributions, there is a threshold policy that is $\frac{1}{2}$-robust, which is tight for the setting; and (3) for log-concave (but non-identical) reward distributions, the $\frac{1}{2}$-robustness can also be achieved under certain regularity assumptions.

PDF Details DOI

STOC Conference 2023 Conference Paper

A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths

Julia Chuzhoy
Ruimin Zhang

We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. Given an n -vertex graph G with non-negative edge lengths, that undergoes an online sequence of edge insertions and deletions, the goal is to support approximate distance queries and shortest-path queries. We provide a deterministic algorithm for this problem, that, for a given precision parameter є, achieves approximation factor (loglog n ) 2 O (1/є 3 ) , and has amortized update time O ( n є log L ) per operation, where L is the ratio of longest to shortest edge length. Query time for distance-query is O (2 O (1/є) · log n · loglog L ), and query time for shortest-path query is O (| E ( P )|+2 O (1/є) · log n · loglog L ), where P is the path that the algorithm returns. To the best of our knowledge, even allowing any o ( n )-approximation factor, no adaptive-update algorithms with better than Θ( m ) amortized update time and better than Θ( n ) query time were known prior to this work. We also note that our guarantees are stronger than the best current guarantees for APSP in decremental graphs in the adaptive-adversary setting.

Details

FOCS Conference 2020 Conference Paper

Pandora's Box with Correlations: Learning and Approximation

Shuchi Chawla 0001
Evangelia Gergatsouli
Yifeng Teng
Christos Tzamos
Ruimin Zhang

The Pandora's Box problem and its extensions capture optimization problems with stochastic input where the algorithm can obtain instantiations of input random variables at some cost. To our knowledge, all previous work on this class of problems assumes that different random variables in the input are distributed independently. As such it does not capture many real-world settings. In this paper, we provide the first approximation algorithms for Pandora's Box-type problems with correlations. We assume that the algorithm has access to samples drawn from the joint distribution on input. Algorithms for these problems must determine an order in which to probe random variables, as well as when to stop and return the best solution found so far. In general, an optimal algorithm may make both decisions adaptively based on instantiations observed previously. Such fully adaptive (FA) strategies cannot be efficiently approximated to within any sub-linear factor with sample access. We therefore focus on the simpler objective of approximating partially adaptive (PA) strategies that probe random variables in a fixed predetermined order but decide when to stop based on the instantiations observed. We consider a number of different feasibility constraints and provide simple PA strategies that are approximately optimal with respect to the best PA strategy for each case. All of our algorithms have polynomial sample complexity. We further show that our results are tight within constant factors: better factors cannot be achieved even using the full power of FA strategies.

Details