Stochastic approximation algorithms for DR-submodular maximization with convex functional constraints
Article Download View Stochastic approximation algorithms for DR-submodular maximization with convex functional constraints
Dachuan Xu
Simultaneous approximation of multi-criteria submodular function maximization
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
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
Approximation Bounds for Quadratic Maximization with Semidefinite Programming Relaxation
In this paper, we consider a class of quadratic maximization problems. One important instance in that class is the famous quadratic maximization formulation of the max-cut problem studied by Goemans and Williamson. Since the problem is NP-hard in general, following Goemans and Williamson, we apply the approximation method based on the semidefinite programming (SDP) relaxation. … Read more
A Note on Approximating the 2-Catalog Segmentation Problem
We present a $.73$-approximation algorithm for a disjoint $2$-Catalog Segmentation and $.63$-approximation algorithm for the joint version of the problem. Previously best known results are $.65$ and $.56$, respectively. The results are based on semidefinite programming and a subtle rounding method. Citation Working Paper, Department of Management Sciences, Henry, B. Tippie College of Business, The … Read more