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

DOI10.1007/s10878-022-00914-6zbMath1505.90116OpenAlexW4296630884MaRDI QIDQ2091111

Qian Liu, Yang Zhou, Min Li, Xiao-Juan Zhang

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) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Numerical methods for solving linear least squares problems
• Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints
• Adaptive Sampling for k-Means Clustering
• An analysis of approximations for maximizing submodular set functions—I
• Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
• Preservation of Supermodularity in Parametric Optimization: Necessary and Sufficient Conditions on Constraint Structures
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• The adaptive complexity of maximizing a submodular function
• Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Near-Optimal Column-Based Matrix Reconstruction
• On the Power of Adaptivity in Sparse Recovery
• A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters

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