Greedy minimization of weakly supermodular set functions

DOI10.4230/LIPICS.APPROX-RANDOM.2017.19MaRDI QIDQ5002622zbMATH OpenFDO

Authors Edo Liberty, Maxim Sviridenko

Publication date 28 July 2021

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2017.19

zbMATH Keywords

data mininggreedy algorithmsmachine learningweak supermodularity

Mathematics Subject Classification ID

Generalized linear models (logistic models) (62J12) Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)

Recommendations

• An approximation guarantee of the greedy descent algorithm for minimzing a supermodular set function.
• Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy
• Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
• Restricted strong convexity implies weak submodularity
• Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

Cites work

• A unified framework for approximating and clustering data
• Adaptive Sampling for k-Means Clustering
• An analysis of approximations for maximizing submodular set functions—I
• Bi-criteria linear-time approximations for generalized k-mean/median/center
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• Matrix approximation and projective clustering via volume sampling
• Near-optimal column-based matrix reconstruction
• Numerical methods for solving linear least squares problems
• Some Applications of the Rank Revealing QR Factorization
• Sparse Approximate Solutions to Linear Systems

Cited in

(9)

• Restricted strong convexity implies weak submodularity
• Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy
• Bi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraint
• The ordered \(k\)-median problem: surrogate models and approximation algorithms
• scientific article; zbMATH DE number 1353835 (Why is no real title available?)
• Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
• An approximation guarantee of the greedy descent algorithm for minimzing a supermodular set function.
• The seeding and bi-criteria algorithms for fuzzy k-median problem
• Budget and profit approximations for spanning tree interdiction

Describes a project that uses

Uses Software

• k-means++

This page was built for publication: Greedy minimization of weakly supermodular set functions

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