Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy

DOI10.1007/S10878-022-00914-6MaRDI QIDQ2091111zbMATH OpenOpenAlexFDO

Authors Xiaojuan Zhang, Qian Liu, M. Li, Yang Zhou

Publication date 31 October 2022

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-022-00914-6

zbMATH Keywords

bi-criteriasupermodularfuzzy \(C\)-means problemgroup sparse linear regression problemnon-supermodular

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25) Parallel algorithms in computer science (68W10)

Recommendations

• Bi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraint
• Greedy minimization of weakly supermodular set functions
• Fast algorithms for maximizing monotone nonsubmodular functions

Cites work

• A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters
• Adaptive Sampling for k-Means Clustering
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• An analysis of approximations for maximizing submodular set functions—I
• Greedy minimization of weakly supermodular set functions
• Near-optimal column-based matrix reconstruction
• Numerical methods for solving linear least squares problems
• On the Power of Adaptivity in Sparse Recovery
• Preservation of supermodularity in parametric optimization: necessary and sufficient conditions on constraint structures
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular maximization with nearly optimal approximation, adaptivity and query complexity
• The adaptive complexity of maximizing a submodular function
• Trading accuracy for sparsity in optimization problems with sparsity constraints

Cited in

(2)

• Bi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraint
• Greedy minimization of weakly supermodular set functions

This page was built for publication: Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2091111)