@techreport{TD:100246, att_abstract={{We introduce Capacitated Metric Labeling. As in Metric Labeling, we are given a weighted graph G = (V, E), a label set L, a semimetric d_L on this label set, and an assignment cost function phi: V x L -> R, and the goal, as in Metric Labeling, is to find an assignment f: V->L that minimizes a particular two-cost function, but in Capacitated Metric Labeling with the additional restriction that each label t_i receive at most l_i nodes. We give a O(log |V|)-approximation algorithm when the number of labels is fixed. We prove that it is impossible to approximate the value of an instance of Capacitated Metric Labeling to within any finite factor, if P!=NP. Furthermore, we prove that any finite-ratio polynomial-time approximation algorithm must multiplicatively violate the label capacities by Omega((log |L|)^(1/2-eps)). }}, att_authors={hk1971, mh0357}, att_categories={}, att_copyright={{SIAM}}, att_copyright_notice={{The definitive version was published in ACM-SIAM Symposium on Discrete Algorithms (SODA) {{, 2011-01-23}}}}, att_donotupload={}, att_private={false}, att_projects={}, att_tags={}, att_techdoc={true}, att_techdoc_key={TD:100246}, att_url={http://web1.research.att.com:81/techdocs_downloads/TD:100246_DS1_2010-10-27T12:53:28.670Z.pdf}, author={Howard Karloff and Mohammad Hajiaghayi and Matthew Andrews and Ankur Moitra}, institution={{ACM-SIAM Symposium on Discrete Algorithms (SODA)}}, month={January}, title={{Capacitated Metric Labeling}}, year=2011, }