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. Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid
 
research article

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

Karaca, O.
•
Tihanyi, D.
•
Kamgarpour, Maryam  
2021
Operations Research Letters

This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and sensor placement problems in control, task allocation problems, video summarization, and many others. We study two greedy heuristics, namely, the forward and reverse greedy. We provide two novel performance guarantees for the approximate solutions obtained by them depending on both submodularity ratio and curvature. © 2021 The Author(s)

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

1-s2.0-S0167637721001462-main.pdf

Type

Publisher's Version

Version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

License Condition

CC BY-NC-ND

Size

367.37 KB

Format

Adobe PDF

Checksum (MD5)

84963594c8c3a71c373a099a69755377

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