arXiv preprint ·
A Tardos-Type Algorithm for Separable Convex Quadratic Programming
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give an exact algorithm for continuous separable convex quadratic programming with an integer equality matrix and nonnegative variables. The number of rational arithmetic operations and comparisons is polynomial in the dimensions and the encoding length of the constraint matrix, independently of the right-hand side, linear costs, and all nonnegative quadratic weights. Intermediate rational encodings are polynomial in the complete input. This yields a strongly polynomial algorithm for every integer matrix class with polynomially bounded entry encodings, including arbitrary matrices with entries in $\{0,\pm1\}$. The local solver compresses a quadratic objective on an integer box and solves only the compressed continuous problem. Two-sided proximity on boxes with rational bounds transfers its solution to a nearby original optimum; integer optima are used only in the proof. A single linear program supplies an error bound and a dual potential, while tight-coordinate revelation and fixed feasible anchors ensure termination and control encoding lengths. An explicit lifting extends the result to convex piecewise quadratic functions of signed integer affine features, with operation counts independent of breakpoints and objective coefficients. Applications include continuous multicommodity flow with shared capacities and piecewise quadratic costs of aggregate congestion.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Fast mixing of the SYK model at high temperatures
Explicit Asymptotic Bounds for Sequential Calibration Beyond $T^{2/3}$
Near-Exact Computation of Independent Chip Model Placement Probabilities for Thousands of Players
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
Improved Sublinear Algorithms for Maximal Independent Set and Metric Steiner Forest
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.