Yinchen Liu 0001

dblp:363/3766-1 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2026
0009-0006-1571-3400ORCID · conflict

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 since 2021
YearPublicationVenuePosition
2026 On the positive and negative p -energies of graphs under edge addition
Quanyu Tang, Yinchen Liu 0001, Wei Wang 0032
Discret. Appl. Math.2
2025 Adaptivity Gaps for Stochastic Probing with Subadditive Functions
abstract
In this paper, we study the stochastic probing problem under a general monotone norm objective. We are given a ground set $U=[n]=\{1,2, \ldots, n\}$, where each element i is associated with an independent nonnegative random variable $X_{i}$ (with a known distribution). We may probe these elements adaptively, and upon probing an element i, its value $X_{i}$ is realized. The sequence of probed elements must satisfy a prefix-closed feasibility constraint $\mathcal{F}$, such as a matroid, an orienteering constraint, or any other downward-closed constraint. We also have a monotone norm function $f: \mathbb{R}_{\geq 0}^{n} \rightarrow \mathbb{R}_{\geq 0}$. Let $P \subseteq U$ be the set of probed elements. Then the reward is $f\left(X_{P}\right)$, where $X_{P}$ is an n-dimensional vector whose i-th coordinate equals the realized value of $X_{i}$ if $i \in P$ (i.e., element i is probed), and 0 otherwise. Our objective is to design a probing strategy that maximizes the expected reward $\mathbb{E}\left[f\left(X_{P}\right)\right]$. We study the adaptivity gap of the problem, defined as the ratio between the expected reward of an optimal adaptive strategy and that of an optimal non-adaptive strategy. A small adaptivity gap allows us to focus on designing nonadaptive strategies, which are typically simpler to represent and analyze. Establishing tight adaptivity gaps is a central challenge in stochastic combinatorial optimization and has been studied extensively for stochastic probing problems with various objective functions. In this paper, we resolve a central open problem in this line of research, posed in [1], [2], by proving that the adaptivity gap for stochastic probing with general monotone norms is bounded by $O\left(\log ^{2} n\right)$. With a refined analysis, we can further strengthen the bound to $O(\log r \log n / \log \log n)$ where r is the maximum length of a sequence in the feasibility constraint ($2 \leq r \leq n$). As a by-product, we obtain an asymptotically tight adaptivity gap $\Theta(\log n / \log \log n)$ for Bernoulli stochastic probing with binary-XOS objectives, matching the lower bound in [1]. We also obtain an $O\left(\log ^{3} n\right)$ upper bound for Bernoulli stochastic probing with general subadditive objectives. Furthermore, for monotone symmetric norms, we prove that the adaptivity gap can be bounded by $O(1)$, answering an open question posed in [3] and improving upon their $O(\log n)$ upper bound. Index Terms-stochastic probing, adaptivity gap, subadditive objective
Jian Li 0015, Yinchen Liu 0001
FOCS2