A flow-dependent quadratic steiner tree problem in the Euclidean plane

Abstract

We introduce a flow-dependent version of the quadratic Steiner tree problem in the plane. An instance of the problem on a set of embedded sources and a sink asks for a directed tree T spanning of these nodes and a bounded number of Steiner points, such that e E (T) f (e) | e | 2 is a minimum, where f(e) is the flow on edge e. The edges are uncapacitated and the flows are determined additively, that is, the flow on an edge leaving a node u will be the sum of the flows on all edges entering u. Our motivation for studying this problem is its utility as a model for relay augmentation of wireless sensor networks. In these scenarios, one seeks to optimize power consumption - which is predominantly..