Linear programming without the matrix

DOI10.1145/167088.167127MaRDI QIDQ5248478zbMATH OpenOpenAlexFDO

Authors Mihalis Yannakakis, Christos 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) Linear programming (90C05) Decision theory (91B06)

Cited in

(18)

• Two sensitivity theorems in fuzzy integer programming.
• Delayed information and action in on-line algorithms
• Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
• On the distributed decision-making complexity of the minimum vertex cover problem
• Distributed distance-bounded network design through distributed convex programming
• A distributed voting scheme to maximize preferences
• Solving linear programming with constraints unknown
• The \(k\)-server problem
• Decomposition algorithms for data placement problem based on Lagrangian relaxation and randomized rounding
• Distributed near-optimal matching
• Fair packing and covering on a relative scale
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• Algorithmic mechanism design
• Minimum vertex cover, distributed decision-making, and communication complexity
• Analysing local algorithms in location-aware quasi-unit-disk graphs
• Local approximability of max-min and min-max linear programs
• A simple distributed algorithm for sparse fractional covering and packing problems
• A simple local 3-approximation algorithm for vertex cover

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5248478)