# Discrete Optimization of Min-Max Violation and its Applications Across Computational Sciences

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 41 references that are in the map.
- First posted on arXiv 19 Aug 2025.

## Builds on (most cited first, 8 of 8)

- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [OmniQuant: Omnidirectionally Calibrated Quantization for Large Language Models](https://mlsanity.com/paper/2308.13137/) (2023)
- [BiLLM: Pushing the Limit of Post-Training Quantization for LLMs](https://mlsanity.com/paper/2402.04291/) (2024)
- [Low-Rank Matrix Approximation in the Infinity Norm](https://mlsanity.com/paper/1706.00078/) (2017)
- [Enhancing Ultra-Low-Bit Quantization of Large Language Models Through Saliency-Aware Partial Retraining](https://mlsanity.com/paper/2504.13932/) (2025)
- [A Convex Formulation for Binary Tomography](https://mlsanity.com/paper/1807.09196/) (2018)

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

- [Sliced-Wasserstein Distribution Alignment Loss Improves the Ultra-Low-Bit Quantization of Large Language Models](https://mlsanity.com/paper/2601.07878/) (2026)

## Abstract (arXiv)

We introduce the Discrete Min-Max Violation (DMMV) as a general optimization problem which seeks an assignment of discrete values to variables that minimizes the largest constraint violation. This context-free mathematical formulation is applicable to a wide range of use cases that have worst-case performance requirements. After defining the DMMV problem mathematically, we explore its properties to establish a foundational understanding. To tackle DMMV instance sizes of practical relevance, we develop a GPU-accelerated heuristic that takes advantage of the mathematical properties of DMMV for speeding up the solution process. We demonstrate the versatile applicability of our heuristic by solving three optimization problems as use cases: (1) post-training quantization of language models, (2) discrete tomography, and (3) Finite Impulse Response (FIR) filter design. In quantization without outlier separation, our heuristic achieves 14% improvement on average over existing methods. In discrete tomography, it reduces reconstruction error by 16% under uniform noise and accelerates computations by a factor of 6 on GPU. For FIR filter design, it nearly achieves 50% ripple reduction compared to using the commercial integer optimization solver, Gurobi. Our comparative results point to the benefits of studying DMMV as a context-free optimization problem and the advantages that our proposed heuristic offers on three distinct problems. Our GPU-accelerated heuristic will be made open-source to further stimulate research on DMMV and its other applications. The code is available at https://anonymous.4open.science/r/AMVM-5F3E/