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 integerk, an approximation factor\alpha, and a diversity measure\sigmaon a set of solutions to an optimization problemP, find a set ofksolutions toPthat(a)are all\alpha-approximately-optimal forPand(b)maximize the diversity measure\sigmaover all such sets ofksolutions. 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\sigmaofksolutions is the sum of the pairwise Hamming distance between the bit-vectors representing theksolutions. 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 differentvalues 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.

Wealsodesign 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.