Approximation Algorithm for Fair Allocation
Project Description

In distributing resources to players, it is the goal to optimize some social utility. In this project, we will implement an approximation algorithm for maximizing the fairness, in the sense that the minimum value of resources assigned to any player is approximately maximized. The optimum is computationally hard to obtain, but one can compute a lower bound using linear programming. Thus, we can also conduct performance evaluation against this lower bound.

CHENG Siu Wing
Course type
Applicant's Roles

The students are expected to be proficient in C++ programming.

There are public libraries for maximum graph matching and linear programming. The students are expected to use these libraries to solve some subproblems, while focusing on implementing the combinatorial approximation algorithm and performance evaluation.

Applicant's Learning Objectives

- learn to use public libraries for maximum graph matching and linear programming which are common optimization subprolblems that arise in practice.
- learn some useful techniques in combinatorial graph algorithms.
- gain experience in conducting performance evaluation.

Complexity of the project