Greedy Optimization

Latest papers

12 papers2 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?
Oct 18, 2026Qixin Zhang, Shi Fu, Shengminjie Chen +2Greedy Optimization Submodular Optimization
College of Computing and Data Science, Nanyang Technological University, Singapore · Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China
CLIPPER Beyond Shortlisting: Auditable Decision Support for Changing Municipal Micromobility Policies
Sep 30, 2026Julian Teusch, Jörg Philipp Müller, Monika SesterCombinatorial Optimization Urban Planning
Institute of Computer Science Clausthal University of Technology Clausthal-Zellerfeld, Germany · Institute of Cartography and Geoinformatics Leibniz University Hannover Hannover, Germany
Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates
Sep 16, 2026Yingquan, Wu, Jason CongCombinatorial Optimization Greedy Optimization
Cody · MBZUAI Institute of Foundation Models Sunnyvale, CA, USA · University of California, Los Angeles Los Angeles, CA, USA
CLIPPER: Replayable Shortlisted Optimization for Repeated Spatial Coverage Planning
Aug 27, 2026Julian Teusch, Jörg Philipp Müller, Monika SesterGreedy Optimization Constrained Optimization
Institute of Computer Science, Clausthal University of Technology, Germany · Institute of Cartography and Geoinformatics, Leibniz University Hannover, Germany
Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning
Aug 12, 2026Vaneet AggarwalSubmodular Optimization Combinatorial Multi-Armed Bandits
V. Aggarwal is with Purdue University, West Lafayette IN, USA
Why does Greedy Search produce Optimal Clustering Outcomes? A Fixed-Core Assignment Theory
Jul 27, 2026Kaifeng Zhang, Kai Ming Ting, Sanjay ChawlaClustering Unsupervised Clustering
School of Artificial Intelligence Nanjing University, China · Qatar Computing Research Institute, HBKU
Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency
Jul 7, 2026Manish Kolachalam, Rani MalhotraVehicle Routing Greedy Optimization
Autonomous Machines Applied Research Center Infosys Center for Imaging Technologies, Infosys Bengaluru, India
Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation
Jun 25, 2026Michael T. M. EmmerichSubmodular Optimization Approximation Algorithms
Learning Interpretable Point-Based Clinical Risk Scores via Direct Optimization
May 18, 2026Ying Cui, Albert M Li, Vivek Charu +3Interpretable ML Greedy Optimization
Department of Biomedical Data Science, Stanford University · Decatur High School · Department of Pathology, Stanford University School of Medicine +1
Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
May 8, 2026Yixin Chen, Alan KuhnleSubmodular Optimization Approximation Algorithms
Department of Computer Science & Engineering, Texas A&M University
Greedy Approaches for Packing While Travelling with Deterministic and Stochastic Constraints
Apr 15, 2026Thilina Pathirage Don, Aneta Neumann, Frank NeumannGreedy Optimization Combinatorial Optimization
Optimisation and Logistics, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia
Greedy Is a Strong Default: Agents as Iterative Optimizers
Mar 28, 2026Yitao LiLarge Language Model-Guided Optimization Black-Box Optimization

Oct 18, 2026J/K move · Enter open · S save

When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?

Qixin Zhang, Shi Fu, Shengminjie Chen, Chao Qian+1

College of Computing and Data Science, Nanyang Technological University, Singapore · Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China

Greedy Optimization Submodular Optimization Approximation Algorithms

Open paper AskPDF arXiv

Weakly submodular maximization finds numerous applications in machine learning, data mining and statistics. In particular, under a cardinality constraint, the standard greedy algorithm is known to attain the tight

(1-e^{-γ})

-approximation guarantee, where

γ

denotes the submodularity ratio. However, when considering general matroid constraints, how well standard greedy can perform has remained a longstanding open question. In this paper, we resolve this question by studying the worst-case approximation guarantee

R_{\mathrm{gr}}(γ,r)

of standard forward greedy, where

r

is the rank of matroid. Specifically, our first contribution is the following refined lower bound \begin{equation*} R_{gr}(γ,r)\ge \max\left{ \fracγ{r}, \frac{γ^2} {B_γ+\sqrt{γ(r-1)}}, \frac{γ^{r+1}} {2-γ+γ^{r+1}}, \frac{γ^2} {14\left(B_γ+\sqrt{γ(1-γ)(r-1)}\right)} \right}, \end{equation*} where

B_γ\triangleq2-γ+γ^2

. This lower bound not only strictly improves upon the previous guarantee of

0.4γ^2/(1+\sqrt{γr})

, but also can recover the classical

1/2

-approximation guarantee at

γ=1

. Subsequently, a corresponding upper bound is established for

R_{\mathrm{gr}}(γ,r)

, namely, \begin{equation}\label{eq_upper_abstract} R_{gr}(γ,r) \le\min\left{\frac{1}{2},20\max\left{\fracγ{r}, \frac{γ^2}{B_γ+ \sqrt{γ(1-γ)(r-1)}}\right}\right}. \end{equation} For every fixed

γ\in(0,1)

, this equation effectively sharpens the recent

O_γ(1/\log(n-1))

upper bound to

O_γ(r^{-1/2})

, where

n

is the size of ground set. Putting all these results together, we eventually can obtain

R_{gr}(γ,r) = Θ\left( \max\left\{\fracγ{r}, \frac{γ^2} {1+\sqrt{γ(1-γ)r}}\right\} \right).