Cover Image

Supermodular Approximation of Norms and Applications

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kesselheim, Thomas, Molinaro, Marco, Singla, Sahil
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives
by: Kesselheim, Thomas, et al.
Published: (2025)

Sample Complexity of Posted Pricing for a Single Item
by: Jin, Billy, et al.
Published: (2024)

Approximating Optimum Online for Capacitated Resource Allocation
by: Braun, Alexander, et al.
Published: (2024)

Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems
by: Segev, Danny, et al.
Published: (2020)

On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

An Efficient Algorithm for Minimizing Ordered Norms in Fractional Load Balancing
by: Blankenburg, Daniel, et al.
Published: (2025)

Online Combinatorial Allocations and Auctions with Few Samples
by: Dütting, Paul, et al.
Published: (2024)

The Power of Migrations in Dynamic Bin Packing
by: Mellou, Konstantina, et al.
Published: (2024)

A Learning Perspective on Random-Order Covering Problems
by: Gupta, Anupam, et al.
Published: (2025)

Submodular Maximization under Supermodular Constraint: Greedy Guarantees
by: Srivastava, Ajitesh, et al.
Published: (2026)

Improved and Oracle-Efficient Online $\ell_1$-Multicalibration
by: Ghuge, Rohan, et al.
Published: (2025)

Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
by: Rubinstein, Aviad, et al.
Published: (2026)

Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering
by: Cao, Nairen, et al.
Published: (2024)

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
by: Kaul, Matthias, et al.
Published: (2025)

FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives
by: Gadekar, Ameet
Published: (2026)

Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
by: Harb, Elfarouk, et al.
Published: (2025)

Online Graph Balancing and the Power of Two Choices
by: Bansal, Nikhil, et al.
Published: (2026)

Prophet and Secretary at the Same Time
by: Kehne, Gregory, et al.
Published: (2025)

Bandit Sequential Posted Pricing via Half-Concavity
by: Singla, Sahil, et al.
Published: (2023)

Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding
by: Anderson, Prashanti, et al.
Published: (2026)

Online Combinatorial Optimization with Graphical Dependencies
by: Gao, Zhimeng, et al.
Published: (2025)

New Algorithms and Lower Bounds for Streaming Tournaments
by: Ghosh, Prantar, et al.
Published: (2024)

Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized Methods
by: Huang, Yufan, et al.
Published: (2023)

Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
by: Kulik, Ariel, et al.
Published: (2019)

Improved Online Load Balancing in the Two-Norm
by: Borst, Sander, et al.
Published: (2025)

Contextual Learning for Stochastic Optimization
by: Heuser, Anna, et al.
Published: (2025)

Single-Sample and Robust Online Resource Allocation
by: Ghuge, Rohan, et al.
Published: (2025)

Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
by: Arndt, Stephen, et al.
Published: (2026)

Approximating $q \rightarrow p$ Norms of Non-Negative Matrices in Nearly-Linear Time
by: Objois, Étienne, et al.
Published: (2025)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
by: Cohen-Addad, Vincent, et al.
Published: (2022)

Minimizing $\ell_2$ Norm of Flow Time by Starvation Mitigation
by: Kuo, Tung-Wei
Published: (2021)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
by: Chitnis, Rajesh, et al.
Published: (2024)

A Modern Approach to Electoral Delimitation using the Quadtree Data Structure
by: Kale, Sahil, et al.
Published: (2024)

New Results on a General Class of Minimum Norm Optimization Problems
by: Chen, Kuowen, et al.
Published: (2025)

Improved Mechanisms and Prophet Inequalities for Graphical Dependencies
by: Livanos, Vasilis, et al.
Published: (2024)

The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms
by: Manoj, Naren Sarayu, et al.
Published: (2023)

Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications
by: De Marco, Gianluca, et al.
Published: (2025)

Approximating $δ$-Covering
by: Hartmann, Tim A., et al.
Published: (2024)

On Approximating Cutwidth and Pathwidth
by: Bansal, Nikhil, et al.
Published: (2023)

Optimized 2-Approximation of Treewidth
by: Belbasi, Mahdi, et al.
Published: (2024)