Seminars

View all Seminars  |  Download ICal for this event

Modern Combinatorial Optimization Problems; Balanced Clustering and Fair Knapsack

Series: M.Tech (Research) Colloquium

Speaker: Mr. Deval Patel M.Tech (Research) Dept. of CSA

Date/Time: Jan 27 09:00:00

Location: CSA Class (Room No. 252, First Floor)

Faculty Advisor: Dr. Anand Louis

Abstract:
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 a client. Algorithms optimizing such objectives might output a solution where few clusters have very large cost and few clusters have a very small cost. Cost-balanced k-clustering problem aims to obtain the clustering which is cost balanced. We consider objective of minimizing maximum cost of each cluster, where the cost of a cluster is 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. We give hardness result. We also define the more general version of the problem and name it

Speaker Bio:

Host Faculty: