Maximizing the overall end-user satisfaction of data broadcast in wireless mesh networks

We show that the problem can be solved by serving the end-users according to a suitable K segmentation, which is a K partition of the end-users that preserves a specific end-user order. When the access points and the end-users have a unique interface, the optimal segmentation can be found in O(N(K+log⁡N)) time by exploiting the convex Monge property of the satisfaction function. When both access points and end-users are equipped with multiple interfaces, the problem becomes computationally intractable, even for a single access point. Polynomial time algorithms are then devised for optimally solving some meaningful particular cases.