Abstract: We study diverse solutions to optimization problems and design algorithms for fair scheduling of demands with priorities on wireless networks.

The problem of finding several sufficiently-diverse, yet approximately optimal solutions to an optimization problem can be described as follows: given an integer k, an approximation factor \alpha, and a diversity measure \sigma on a set of solutions to an optimization problem P, find a set of k solutions to P that (a) are all \alpha-approximately-optimal for P and (b) maximize the diversity measure \sigma over all such sets of k solutions. The optimization problems considered here are maximum matching, spanning tree, global min-cut, shortest path, and minimum weight bases of a matroid. Here, a solution is a set of edges, and the number of edges two given solutions differ in as the diversity measure of the pair. The diversity measure \sigma of k solutions is the sum of the pairwise Hamming distance between the bit-vectors representing the k solutions. We propose the first polynomial-time algorithms that (except for the unweighted spanning tree), for these five graph problems, guarantee that their diversity is at least 1/4 times the optimal diversity under different values of \alpha. This result is applied for minimum weight bases of a matroid, which means it gives us diverse \alpha-approximate minimum spanning trees, advancing a step towards achieving diverse \alpha-approximate TSP tours.

We also design algorithms for fair scheduling of prioritized demands on wireless networks. We consider multi-channel, multi-radio scheduling at the MAC layer to optimize for the performance of prioritized, delay-sensitive demands. Our objective is to design an interference-free schedule that minimizes the maximum weighted refresh time among all edges, where the refresh time of an edge is the maximum number of time slots between two successive slots of that edge and the weights reflect given priorities. In the single-antenna unweighted case, we show that the scheduling problem reduces to different edge coloring problems under different cases. For the multi-antenna weighted case, We provide a randomized algorithm with an expected approximation factor guarantee. We evaluate the performance of our methods in different settings using simulations.