Li Yu

Simultaneous approximation of multi-criteria submodular function maximization

  • Donglei Du
  • Dachuan Xu
  • Naihua Xiu
  • Li Yu
    • Categories Approximation Algorithms, Game Theory, Multi-Criteria Optimization Tags , , ,

    Recently there has been intensive interest on approximation of the NP-hard submodular maximization problem due to their theoretical and practical significance. In this work, we extend this line of research by focusing on the simultaneous approximation of multiple submodular function maximization. We address existence and nonexistence results for both deterministic and randomized approximation when the … Read more

    Improved approximation algorithms for the facility location problems with linear/submodular penalty

  • Donglei Du
  • Dachuan Xu
  • Naihua Xiu
  • Li Yu
    • Categories Approximation Algorithms Tags

    We consider the facility location problem with submodular penalty (FLPSP) and the facility location problem with linear penalty (FLPLP), two extensions of the classical facility location problem (FLP). First, we introduce a general algorithmic framework for a class of covering problems with submodular penalty, extending the recent result of Geunes et al. [12] with linear … Read more