Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Submodular Stochastic Probing on Matroids
 
research article

Submodular Stochastic Probing on Matroids

Adamczyk, Marek
•
Sviridenko, Maxim
•
Ward, Justin
2016
Mathematics of Operations Research

In a stochastic probing problem we are given a universe E, and a probability that each element e in E is active. We determine if an element is active by probing it, and whenever a probed element is active, we must permanently include it in our solution. Moreover, throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. All previous algorithmic results in this framework have considered only the problem of maximizing a linear function of the active elements. Here, we consider submodular objectives. We provide new, constant-factor approximations for maximizing a monotone submodular function subject to multiple matroid constraints on both the elements that may be taken and the elements that may be probed. We also obtain an improved approximation for linear objective functions, and show how our approach may be generalized to handle k-matchoid constraints.

  • Details
  • Metrics
Type
research article
DOI
10.1287/moor.2015.0766
Author(s)
Adamczyk, Marek
Sviridenko, Maxim
Ward, Justin
Date Issued

2016

Publisher

INFORMS

Published in
Mathematics of Operations Research
Volume

41

Issue

3

Start page

1022

End page

1038

Subjects

stochastic optimization

•

submodular maximization

•

matroids

•

iterative rounding

•

stochastic matching

•

sequential posted pricing

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL2  
Available on Infoscience
August 3, 2017
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/139536
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés