Seminars
View all Seminars | Download ICal for this eventModern 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: