Motivated by real-world applications such as the allocation of public housing, we examine the problem of assigning a group of agents to vertices (e.g., spatial locations) of a network so that the diversity level is maximized. Specifically, agents are of two types (characterized by features), and we measure diversity by the number of agents who have at least one neighbor of a different type. This problem is known to be NP-hard, and we focus on developing approximation algorithms with provable performance guarantees. We first present a local-improvement algorithm for general graphs that provides an approximation factor of 1/2. For the special case where the sizes of agent subgroups are similar, we present a randomized approach based on semidefinite programming that yields an approximation factor better than 1/2. Further, we show that the problem can be solved efficiently when the underlying graph is treewidth-bounded and obtain a polynomial time approximation scheme (PTAS) for the problem on planar graphs. Lastly, we conduct experiments to evaluate the per-performance of the proposed algorithms on synthetic and real-world networks.
翻译:在公共住房分配等现实应用的推动下,我们研究将一组物剂分配到网络的脊椎(例如空间位置)的问题,以便最大限度地提高多样性水平。具体地说,物剂有两种类型(特征特征特征特征特征特征特征),我们用至少有不同类型邻居的物剂数量来衡量多样性。众所周知,这个问题是NP硬的,我们侧重于开发具有可辨识性能保障的近似算法。我们首先为提供近似系数1/2的一般图表提供局部改进算法。对于具有类似物剂子群规模的特例,我们根据半定型编程提供一种随机化方法,产生比1/2更好的近似系数。此外,我们表明,当基本图以树木为界标定时,问题就能得到有效解决,并获得关于平面图问题的多数值时间近比法(PTAS)。最后,我们进行实验,以评价在合成和现实世界网络上拟议的算算法的每个运行情况。</s>