2022/11/15 by Sungjin Im, Im, Sungjin, Benjamin Moseley +7
Computer Science · Engineering · Mathematics · #Advanced Control Systems Optimization #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.2211.08381
openalex publication_date 2022/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a class of optimization problems that involve determining the maximum value that a function in a particular class can attain subject to a collection of difference constraints. We show that a particular linear programming technique, based on duality and projections, can be used to rederive some structural results that were previously established using more ad hoc methods. We then show that this technique can be used to obtain a polynomial-time algorithm for a certain type of simple difference constraints. Finally we give lower bound results that show that certain possible extensions of these results are probably not feasible.