Home » Publication » 27969

Dettaglio pubblicazione

2023, Leibniz International Proceedings in Informatics, Pages - (volume: 275)

Submodular Norms with Applications To Online Facility Location and Stochastic Probing (04b Atto di convegno in volume)

Patton K., Russo M., Singla S.

Optimization problems often involve vector norms, which has led to extensive research on developing algorithms that can handle objectives beyond the ℓ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 ℓ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 ℓ1 norm and inner symmetric norms.
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma