mlsanityData to 14 Oct 2026

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

arXiv 2508.13437 ↗First posted 19 Aug 2025cs.AIcited by 1

Not on the map. Why?

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/

Key facts. Cited by 1 paper 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

8 of 41 references.

References · 8

  1. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,512
  2. 2021Convex optimizationcited by 2,515
  3. 2022GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformerscited by 1,919
  4. 2023OmniQuant: Omnidirectionally Calibrated Quantization for Large Language Modelscited by 424
  5. 2024BiLLM: Pushing the Limit of Post-Training Quantization for LLMscited by 144
  6. 2017Low-Rank Matrix Approximation in the Infinity Normcited by 5
  7. 2025Enhancing Ultra-Low-Bit Quantization of Large Language Models Through Saliency-Aware Partial Retrainingcited by 3
  8. 2018A Convex Formulation for Binary Tomographycited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Sliced-Wasserstein Distribution Alignment Loss Improves the Ultra-Low-Bit Quantization of Large Language Modelscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026The Devil Is in the Reconstruction Loss Scale: Rethinking Optimization in LLM Quantization
  2. 2026ScaleSweep: Accurate NVFP4 Post-Training Quantization of LLMs via Block Scale Initialization
  3. 2024Accurate Block Quantization in LLMs with Outliers
  4. 2023Fast and Efficient 2-bit LLM Inference on GPU: 2/4/16-bit in a Weight Matrix with Asynchronous Dequantization
  5. 2025The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm
  6. 2025NeUQI: Near-Optimal Uniform Quantization Parameter Initialization for Low-Bit LLMs
  7. 2026Deterministic LLM Inference Across GPU Kernels: Power-of-Two INT8 Quantization Scales and the Limits of Tolerance-Based Conformance
  8. 2026ScaleBITS: Scalable Bitwidth Search for Hardware-Aligned Mixed-Precision LLMs