Restricted Max-Min Allocation

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Defense

Title: "Restricted Max-Min Allocation"

by

FENG Xuming

Abstract:

The restricted max-min fair allocation problem seeks an allocation of 
resources to players that maximizes the minimum total value obtained by 
any player. It is NP-hard to approximate the problem to a ratio less than 
2. In 2019, Cheng and Mao constructed an allocation with value within 
factors of 4 + δ from the optimum for any constant δ > 0. The running 
time is polynomial in the input size for any constant δ chosen. In this 
project, we are going to look at the implementations of the algorithm and 
test the performance under different data distributions. In additional, we 
are also going to explore another algorithm that uses linear programming 
and randomized rounding to give an approximation ratio of (log n/log log n).
It is known that LP can be solved in polynomial time. We will develop 
a detailed description of the algorithm and its running time analysis.


Date            : 29 May 2020 (Friday)

Time            : 10:00 - 10:40

Zoom Meeting    : https://hkust.zoom.us/j/98397943304

Advisor         : Prof. CHENG Siu-Wing

2nd Reader      : Dr. ARYA Sunil