Stochastic Probing with Prices

12^th October 2018, 13:00 H223
Dr. Takanori Maehara
RIKEN AIP, Japan
Discrete Optimization Unit

Abstract

A recent trend in combinatorial optimization is Optimization with
Uncertainty. Here, we consider the following setting, called
Stochastic Probing with Prices.
Suppose that we have a combinatorial optimization on a finite set V.
Each element u in V is active (with probability p) or non-active
(otherwise), which is determined by nature. By paying cost c_u, we can
observe whether u is active or not (called "probe"), and if it is
active, it is irrevocably added the solution. The goal is to maximize
an objective function minus the payment, where the solution (= set of
probed active elements) and the set of probed elements satisfy their
constraints.
This problem is a generalization of the Stochastic Probing
(Gupta-Nagarajan, IPCO'13) that does not contain the cost, and the
Price of Information (Singla, SODA'18) that does have constraint on
probed elements. This problem has several applications including
kidney exchange, online dating, and online advertising.
In this study, we propose a method to obtain approximate strategy when
the objective function is submodular and the constraints have low
correlation gaps. The method is based on the continuous greedy
algorithm and the contention resolution scheme.
This is a joint work with Ben Chugg (UBC)

Short bio:

Dr. Takanori Maehara is a Unit Leader (= Associate Professor) of Discrete
Optimization Unit at RIKEN AIP, Japan. He completed his PhD at the
University of Tokyo in 2012. He works on discrete optimization theory,
numerical analysis, and these applications in machine learning and
data mining.