Text
Min-Max-Min Optimization with Smooth and Strongly Convex Objectives
We consider min-max-min optimization with smooth and strongly convex objectives. Our motivation for studying this class of problems stems from its connection to the k-center problem and the growing literature on min-max-min robust optimization. In particular, the considered class of problems nontrivially generalizes the Euclidean k-center problem in the sense that distances in this more general setting do not necessarily satisfy metric properties. We present a 9k-approximation algorithm (where k is the maximum condition number of the functions involved) that generalizes a simple greedy 2-approximation algorithm for the classical k -center problem. We show that for any choice of k , there is an instance with a condition number of k per which our algorithm yields a (4k+4√k+1) -approximation guarantee, implying that our analysis is tight when k = 1. Finally, we compare the computational performance of our approximation algorithm with an exact mixed integer linear programming approach.
Barcode | Tipe Koleksi | Nomor Panggil | Lokasi | Status | |
---|---|---|---|---|---|
art147471 | null | Artikel | Gdg9-Lt3 | Tersedia namun tidak untuk dipinjamkan - No Loan |
Tidak tersedia versi lain