BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20200127T120000Z
UID:1a3c8eab53b3b6738a2898a341eda57d-53
DTSTAMP:19700101T120009Z
DESCRIPTION:Modern Combinatorial Optimization Problems; Balanced Clustering and Fair Knapsack
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/53/modern-combinatorial-optimization-problems-balanced-clustering-and-fair-knapsack/
SUMMARY: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
DTSTART:20200127T120000Z
END:VEVENT
END:VCALENDAR