# Approximation Algorithms for Minimum Norm and Ordered Optimization Problems

arXiv: https://arxiv.org/abs/1811.05022 · HTML: https://mlsanity.com/paper/1811.05022/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2018.

## Built on by (most cited first, 11 of 11)

- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [Navigating the Social Welfare Frontier: Portfolios for Multi-objective Reinforcement Learning](https://mlsanity.com/paper/2502.09724/) (2025)
- [Optimizing Multiple Simultaneous Objectives for Voting and Facility Location](https://mlsanity.com/paper/2212.03467/) (2022)
- [Clustering to Minimize Cluster-Aware Norm Objectives](https://mlsanity.com/paper/2410.24104/) (2024)
- [Online Correlation Clustering: Simultaneously Optimizing All ℓp-norms](https://mlsanity.com/paper/2510.15076/) (2025)
- [A Broader View on Clustering under Cluster-Aware Norm Objectives](https://mlsanity.com/paper/2512.06211/) (2025)

## Abstract (arXiv)

 In many optimization problems, a feasible solution induces a multi-dimensional cost vector. For example, in load-balancing a schedule induces a load vector across the machines. In k-clustering, opening k facilities induces an assignment cost vector across the clients. In this paper we consider the following minimum norm optimization problem : Given an arbitrary monotone, symmetric norm, find a solution which minimizes the norm of the induced cost-vector. This generalizes many fundamental NP-hard problems. We give a general framework to tackle the minimum norm problem, and illustrate its efficacy in the unrelated machine load balancing and k-clustering setting. Our concrete results are the following. bullet We give constant factor approximation algorithms for the minimum norm load balancing problem in unrelated machines, and the minimum norm k-clustering problem. To our knowledge, our results constitute the first constant-factor approximations for such a general suite of objectives. bullet In load balancing with unrelated machines, we give a 2-approximation for the problem of finding an assignment minimizing the sum of the largest ℓ loads, for any ℓ. We give a (2+varepsilon)-approximation for the so-called ordered load-balancing problem. bullet For k-clustering, we give a (5+varepsilon)-approximation for the ordered k-median problem significantly improving the constant factor approximations from Byrka, Sornat, and Spoerhase (STOC 2018) and Chakrabarty and Swamy (ICALP 2018). bullet Our techniques also imply O(1) approximations to the best simultaneous optimization factor for any instance of the unrelated machine load-balancing and the k-clustering setting. To our knowledge, these are the first positive simultaneous optimization results in these settings.