2018/05/29 by Shinsaku Sakaue, Sakaue, Shinsaku
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1805.11251
openalex publication_date 2018/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Maximization of it non-submodular functions appears in various scenarios,\nand many previous works studied it based on some measures that quantify the\ncloseness to being submodular. On the other hand, many practical non-submodular\nfunctions are actually close to being it modular, which has been utilized in\nfew studies. In this paper, we study cardinality-constrained maximization of\n it weakly modular functions, whose closeness to being modular is measured by\n it submodularity and it supermodularity ratios, and reveal what we can\nand cannot do by using the weak modularity. We first show that guarantees of\nmulti-stage algorithms can be proved with the weak modularity, which generalize\nand improve some existing results, and experiments confirm their effectiveness.\nWe then show that weakly modular maximization is it fixed-parameter\ntractable under certain conditions; as a byproduct, we provide a new\ntime--accuracy trade-off for \ℓ0-constrained minimization. We finally\nprove that, even if objective functions are weakly modular, no polynomial-time\nalgorithms can improve the existing approximation guarantees achieved by the\ngreedy algorithm.\n