4 citations · 9 across the 5 of their papers we have counts for
5 papers
Wireless coverage prediction via parametric shortest paths
David Applegate, Aaron Archer, David S. Johnson +3
When deciding where to place access points in a wireless network, it is useful to model the signal propagation loss between a proposed antenna location and the areas it may cover.…
Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs
David S. Johnson, Lee Breslau, Ilias Diakonikolas +6
In this paper we consider two special cases of the "cover-by-pairs" optimization problem that arise when we need to place facilities so that each customer is served by two faciliti…
On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing
Janos Csirik, David S. Johnson, Claire Kenyon
The Sum of Squares algorithm for bin packing was defined in [2] and studied in great detail in [1], where it was proved that its worst case performance ratio is at most 3. In this…
On the Sum-of-Squares Algorithm for Bin Packing
Janos Csirik, David S. Johnson, Claire Kenyon +3
In this paper we present a theoretical analysis of the deterministic on-line {\em Sum of Squares} algorithm () for bin packing introduced and studied experimentally in \cite{CJ…
The Geometric Maximum Traveling Salesman Problem
Alexander Barvinok, Sandor P. Fekete, David S. Johnson +3
We consider the traveling salesman problem when the cities are points in R^d for some fixed d and distances are computed according to geometric distances, determined by some norm.…