Local approximability of max-min and min-max linear programs
type: Item
instance of: scholarly article
title: Local approximability of max-min and min-max linear programs
zbMATH Open document ID: 1253.68360
author: Patrik Floréen
author: Marja Hassinen
author: Joel Kaasinen
author: Petteri Kaski
author: Topi Musto
author: Jukka Suomela
published in: Theory of Computing Systems
publication date: 2012-12-10T00:00:00Z
full work available at URL: http://hdl.handle.net/10138/28034
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C47
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6114782
zbMATH Keywords: approximation algorithms
zbMATH Keywords: distributed algorithms
zbMATH Keywords: linear programs
zbMATH Keywords: local algorithms
MaRDI profile type: Publication
OpenAlex ID: W2011915102
Wikidata QID: Q57540238
cites work: A Local 2-Approximation Algorithm for the Vertex Cover Problem
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Fast Distributed Approximations in Planar Graphs
cites work: Almost stable matchings by truncating the Gale-Shapley algorithm
cites work: Q4250185
cites work: Approximation schemes for covering and packing problems in image processing and VLSI
cites work: The size of bipartite graphs with a given girth
cites work: The price of being near-sighted
cites work: Leveraging Linial’s Locality Limit
cites work: Locality in Distributed Graph Algorithms
cites work: What Can be Computed Locally?
cites work: Linear programming without the matrix
cites work: A simple local 3-approximation algorithm for vertex cover
DOI: 10.1007/S00224-010-9303-6
Recommended article: Q4668647
Recommended article: Q4883380
Recommended article: Q3818813
Recommended article: Local minima of nonconvex problems
Recommended article: Q4394601
Recommended article: Q3171810
Recommended article: Local Convergence Properties of New Methods in Linear Programming
Recommended article: On the number of local maxima in quadratic 0-1 programs
Recommended article: Local minima, marginal functions, and separating hyperplanes in discrete optimization
description: scientific article; zbMATH DE number 6114782