Local approximability of max-min and min-max linear programs

DOI10.1007/s00224-010-9303-6zbMath1253.68360OpenAlexW2011915102WikidataQ57540238 ScholiaQ57540238MaRDI QIDQ693753

Topi Musto, Patrik Floréen, Petteri Kaski, Marja Hassinen, Jukka Suomela, Joel Kaasinen

Publication date: 10 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10138/28034

zbMATH Keywords

approximation algorithmsdistributed algorithmslinear programslocal algorithms

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (7)

Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ A hierarchy of local decision ⋮ Local approximability of max-min and min-max linear programs ⋮ Weak models of distributed computing, with connections to modal logic ⋮ Distributed Distance-Bounded Network Design Through Distributed Convex Programming

Cites Work

• Unnamed Item
• Local approximability of max-min and min-max linear programs
• A simple local 3-approximation algorithm for vertex cover
• The size of bipartite graphs with a given girth
• Almost stable matchings by truncating the Gale-Shapley algorithm
• Fast Distributed Approximations in Planar Graphs
• Leveraging Linial’s Locality Limit
• The price of being near-sighted
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• Approximation schemes for covering and packing problems in image processing and VLSI
• Locality in Distributed Graph Algorithms
• Approximation algorithms for NP-complete problems on planar graphs
• What Can be Computed Locally?
• Linear programming without the matrix

This page was built for publication: Local approximability of max-min and min-max linear programs