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.

Preliminary version appeared in APPROX 2023

References in corpus (9)

• Near-optimal Nonmyopic Value of Information in Graphical Models
• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Non-monotone submodular maximization under matroid and knapsack constraints
• Geometric Mean Metric Learning
• Structured sparsity-inducing norms through submodular functions
• Deep Submodular Functions
• 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