Linear programming without the matrix

DOI10.1145/167088.167127zbMath1310.90073OpenAlexW2027082532MaRDI QIDQ5248478

Mihalis Yannakakis, Christos H. Papadimitriou

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167127

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decision theory (91B06) Linear programming (90C05)

Related Items (17)

Solving Linear Programming with Constraints Unknown ⋮ Minimum vertex cover, distributed decision-making, and communication complexity ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Two sensitivity theorems in fuzzy integer programming. ⋮ The \(k\)-server problem ⋮ Fair Packing and Covering on a Relative Scale ⋮ Decomposition algorithms for data placement problem based on Lagrangian relaxation and randomized rounding ⋮ Local approximability of max-min and min-max linear programs ⋮ Algorithmic mechanism design ⋮ A simple local 3-approximation algorithm for vertex cover ⋮ Efficient distributed approximation algorithms via probabilistic tree embeddings ⋮ Distributed near-optimal matching ⋮ On the distributed decision-making complexity of the minimum vertex cover problem ⋮ A distributed voting scheme to maximize preferences ⋮ Delayed information and action in on-line algorithms ⋮ Distributed Distance-Bounded Network Design Through Distributed Convex Programming

This page was built for publication: Linear programming without the matrix