Submodular Norms with Applications To Online Facility Location and Stochastic Probing

Abstract

Optimization problems often involve vector norms, which has led to extensive research on developing algorithms that can handle objectives beyond the ${\ell }_p$ norms. Our work introduces the concept of submodular norms, which are a versatile type of norms that possess marginal properties similar to submodular set functions. We show that submodular norms can accurately represent or approximate well-known classes of norms, such as ${\ell }_p$ norms, ordered norms, and symmetric norms. Furthermore, we establish that submodular norms can be applied to optimization problems such as online facility location, stochastic probing, and generalized load balancing. This allows us to develop a logarithmic-competitive algorithm for online facility location with symmetric norms, to prove a logarithmic adaptivity gap for stochastic probing with symmetric norms, and to give an alternative poly-logarithmic approximation algorithm for generalized load balancing with outer ${\ell }_1$ norm and inner symmetric norms.

arXiv commentPreliminary version appeared in APPROX 2023

References in corpus (18)

• Near-optimal Nonmyopic Value of Information in Graphical Models
• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Conic geometric optimisation on the manifold of positive definite matrices
• Non-monotone submodular maximization under matroid and knapsack constraints
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives
• Geometric Mean Metric Learning
• Structured sparsity-inducing norms through submodular functions
• Beyond Convexity: Stochastic Quasi-Convex Optimization
• Geodesic Convex Optimization: Differentiation on Manifolds, Geodesics, and Convexity
• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• Submodular Functions: from Discrete to Continous Domains
• Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
• Deep Submodular Functions
• A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns
• Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings
• Non-monotone DR-Submodular Function Maximization
• Non-monotone DR-submodular Maximization: Approximation and Regret Guarantees
• Provable Non-Convex Optimization and Algorithm Validation via Submodularity

Cited by in corpus (1)

• Improved Regret Bounds for Online Submodular Maximization