View all Seminars  |  Download ICal for this event

Modern Combinatorial Optimization Problems: Balanced Clustering and Fair Knapsack

Series: M.Tech (Research) Thesis Defence - ONLINE

Speaker: Mr. Deval PatelM.Tech (Research) studentDept. of CSA

Date/Time: Jul 17 11:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor: Dr. Anand Louis

In many classical optimization problems, it is desirable to have an output that is equitable in some sense. The property equitability could be defined differently for different optimization problems. We study this property in two classical optimization problems, clustering and knapsack. In the clustering problem, we desire to have a cost of the clustering evenly distributed among the clusters. We study this problem under the name cost-balanced k-clustering. In the knapsack problem, we desire to have a packing which is fair in some sense. We study this problem under the name fair knapsack. In most of the clustering objectives like k-median or k-center, the cost of assigning a client to the cluster is considered to be borne by client. Algorithms optimizing such objectives might output a solution where few clusters have very large cost and few clusters have very small cost. Cost-balanced k-clustering problem aims to obtain the clustering which is cost balanced. We consider the objective of minimizing the maximum cost of each cluster, where the cost of a cluster is the sum of distances of all the points in that cluster from the center of that cluster. We define the notion of γ-stability, for γ > 1, for the problem and give a poly time algorithm for 1.5-stable instances of the problem. The algorithm requires an optimal value as an input. We also modify this algorithm for 1.5+eps, eps>0, stable instance that does not require an optimal value as an input. We also define the more general version of the problem and name it "lp" cost-balanced k-clustering. Given a black-box algorithm which gives constant factor approximation to the "lp" cost k-clustering problem, we show a procedure that runs in poly time and gives bi-criteria approximation to the "lp" cost-balanced k-clustering problem.
In this work, we also consider the notion of group fairness in the knapsack problems. In this setting, each item belongs to some category, and our goal is to compute a subset of items such that each category is fairly represented, in addition to the total weight of the subset not exceeding the capacity, and the total value of the subset being maximized. We study various notions of group fairness, such as the number of items from each category, the total value of items from each category, and the total weight of items from each category. We give algorithms and hardness results for these problems.

Microsoft Teams link:

Speaker Bio:

Host Faculty: