Local approximability of max-min and min-max linear programs
DOI10.1007/S00224-010-9303-6zbMATH Open1253.68360OpenAlexW2011915102WikidataQ57540238 ScholiaQ57540238MaRDI QIDQ693753FDOQ693753
Authors: Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, Topi Musto, Jukka Suomela 
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
Recommendations
- scientific article; zbMATH DE number 2156152
- scientific article; zbMATH DE number 895368
- scientific article; zbMATH DE number 4091205
- Local minima of nonconvex problems
- scientific article; zbMATH DE number 1163112
- scientific article; zbMATH DE number 5953654
- Local Convergence Properties of New Methods in Linear Programming
- On the number of local maxima in quadratic 0-1 programs
- Local minima, marginal functions, and separating hyperplanes in discrete optimization
Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Minimax problems in mathematical programming (90C47) Approximation algorithms (68W25) Distributed algorithms (68W15)
Cites Work
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation schemes for covering and packing problems in image processing and VLSI
- Locality in Distributed Graph Algorithms
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- The size of bipartite graphs with a given girth
- Almost stable matchings by truncating the Gale-Shapley algorithm
- Title not available (Why is that?)
- Linear programming without the matrix
- The price of being near-sighted
- A simple local 3-approximation algorithm for vertex cover
- What Can be Computed Locally?
- A Local 2-Approximation Algorithm for the Vertex Cover Problem
- Local approximability of max-min and min-max linear programs
Cited In (9)
- Local minima, marginal functions, and separating hyperplanes in discrete optimization
- A hierarchy of local decision
- Weak models of distributed computing, with connections to modal logic
- Good locally maximal programs for the Robinson–Solow–Srinivasan model
- Fast primal-dual distributed algorithms for scheduling and matching problems
- Analysing local algorithms in location-aware quasi-unit-disk graphs
- Linear-in-\(\varDelta \) lower bounds in the LOCAL model
- Local approximability of max-min and min-max linear programs
- Distributed distance-bounded network design through distributed convex programming
This page was built for publication: Local approximability of max-min and min-max linear programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693753)
