@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,
}