Hamidreza Validi Beginning in the 1960s, techniques from operations research began to be used to generate political districting plans. A classical example is the integer programming model of Hess et al. (Operations Research 13(6):998–1006, 1965). Due to the model’s compactness-seeking objective, it tends to generate contiguous or nearly-contiguous districts, although none of the model’s constraints explicitly impose … Read more
In the paper “A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs” (Networks 39(1):53–60, 2002), Williams introduced an extended formulation for the spanning tree polytope of a planar graph. This formulation is remarkably small (using only $O(n)$ variables and constraints) and remarkably strong (defining an integral polytope). In this note, … Read more
Two nodes of a wireless network may not be able to communicate with each other directly perhaps due to obstacles or insufficient signal strength. This necessitates the use of intermediate nodes to relay information. Often, one designates a (preferably small) subset of them to relay these messages (i.e., to serve as a virtual backbone for … Read more