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

DOI10.1007/S00224-010-9303-6MaRDI QIDQ693753zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

approximation algorithmsdistributed algorithmslocal algorithmslinear programs

Mathematics Subject Classification ID

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)

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

Cites work

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

Cited in

(9)

• Analysing local algorithms in location-aware quasi-unit-disk graphs
• Distributed distance-bounded network design through distributed convex programming
• A hierarchy of local decision
• Linear-in-\(\varDelta \) lower bounds in the LOCAL model
• Local minima, marginal functions, and separating hyperplanes in discrete optimization
• Local approximability of max-min and min-max linear programs
• Weak models of distributed computing, with connections to modal logic
• Fast primal-dual distributed algorithms for scheduling and matching problems
• Good locally maximal programs for the Robinson–Solow–Srinivasan model

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)