  In this paper we present various distributed algorithms for LP-type problems
in the well-known gossip model. LP-type problems include many important classes
of problems such as (integer) linear programming, geometric problems like
smallest enclosing ball and polytope distance, and set problems like hitting
set and set cover. In the gossip model, a node can only push information to or
pull information from nodes chosen uniformly at random. Protocols for the
gossip model are usually very practical due to their fast convergence, their
simplicity, and their stability under stress and disruptions. Our algorithms
are very efficient (logarithmic rounds or better with just polylogarithmic
communication work per node per round) whenever the combinatorial dimension of
the given LP-type problem is constant, even if the size of the given LP-type
problem is polynomially large in the number of nodes.
