Executive Summary : | Combinatorial optimization problems are prevalent in various fields, including operations research, AI/ML, internet advertising, and ride-sharing apps. However, finding quick, exact solutions can be challenging due to computational intractability or uncertainty. To address these issues, researchers propose studying approximation and online algorithms for several important optimization problems.
1. Geometric optimization problems have numerous applications in supply chain management, sensor networks, routing, databases, and bandwidth allocation. The PI has made progress on several open problems in approximation algorithms for geometric problems, such as multidimensional bin packing, geometric knapsack, strip packing, and maximum independent set of rectangles.
2. Fair algorithms for online learning and optimization are increasingly being used to aid decision-making processes, such as granting loans or hiring applicants. However, these algorithms can be biased due to historical marginalization of races. This has led to a surge in algorithmic research efforts from a fairness perspective.
In this proposal, the focus is on fairness for problems in online learning, including meritocracy vs quota, regret, ranking, recommendations, and resource allocation under the group-fairness objective. The study will also consider the notion of fairness in regret, a traditional measure of performance in online learning. In conclusion, combinatorial optimization problems are essential for various applications, but their accuracy and fairness need further investigation. |