- 文献综述（或调研报告）：
Brams S J[1]展示了公平分割问题是如何在多个领域中得到应用的，然后分析了适用于两方以上或一个以上的利益需要分割的情况的公平分割程序，特别是，他们专注于提供“免妒忌”分配的程序，在这些程序中，每个人都认为他或她获得了最大的份额，因此不会妒忌任何其他人。切蛋糕，分割房地产，在国际争端中确定边界——这种公平划分的问题无处不在。公平分工通过对分配货物的各种程序（或“差事”等）的严格分析，或在有争议的情况下决定谁在哪些问题上胜出，来处理所有这些问题以及更多问题。从分析著名的切饼程序“I Cut，You Choose”开始，他们还讨论了不同拍卖和选举程序的公平性。
Woeginger G J [2]研究了一个多项式时间近似方案最大化最小机器完成时间。他们考虑将一组n个作业分配给m个完全相同的并行机器系统的问题，以便最大化最早的机器完成时间（不使用空闲时间）。该问题在组合式燃气涡轮飞机发动机维修行动的排序中有应用。到目前为止，只知道最坏情况比严格远离一的近似算法，文中给出了该问题的第一个多项式时间近似方案。算法的时间复杂度是，其中是一个常数，取决于所需的精度。
Kumar A , Kleinberg J[3]研究资源配置的公平性措施，在许多优化问题中，我们试图将有限的一组资源分配给一组有需求的个人。因此，这种分配自然可以被视为向量，其中一个坐标代表每个单独的坐标。在网络路由和带宽分配工作的推动下，我们考虑了在坐标意义上同时近似所有可行分配的问题。这是一种非常强的“全局”近似保证，我们探讨了它在一系列离散优化问题中的后果，包括设备位置、调度和网络中的带宽分配。在传统的近似算法设计中没有遇到的一个基本问题是，在这个全局意义上，不需要为每个问题实例都存在良好的近似；没有先验的原因，为什么应该有一个同时近似所有其他问题的分配。因此，有关这种良好配置的存在性问题导致了对资源中一些基本问题的新看法。
- Lipton, E. Markakis, E. Mossel and A. Saberi[4]从算法的角度研究了一组不可分割的商品公平分配给一组人的问题。他们关注的标准是嫉妒自由。在我们的模型中，单调效用函数与每一个参与者相关联，为参与者指定商品的每个子集的值。如果每个玩家都喜欢自己的份额而不是其他玩家的份额，那么分配就没有嫉妒之心。当商品可分割时，嫉妒自由分配总是存在的。在存在不可分割性的情况下，他们证明了存在着嫉妒被最大边际效用所约束的分配，并给出了一种计算这种分配的简单算法。然后，将研究寻找一个具有最小可能嫉妒的分配的优化问题。在一般情况下，除非p=np，否则问题在多项式时间内是不可解或近似的。他们考虑与一类作业调度问题密切相关的自然特殊情况（如附加实用程序）。得到了近似算法和不可估计的结果。最后，研究了设计真实机制来产生有界嫉妒分配的问题。
- Golovin[5]也研究了不可分割商品的最大化最小公平分配问题。在这种情况下，公平分配是指最大化任何代理收到的最小效用的分配。文中给出了该问题的几个变量的硬度结果和多项式时间逼近算法。我们的主要结果是在模型中使用加法效用的双标准近似，其中一个部分的代理接收效用至少为OPT/k，对于任何整数k。这个结果是通过舍入问题的适当线性规划松弛得到的，并且是我们的lp的最佳可能结果。对于只有两类货物的特殊情况，我们也给出了近似值，对于具有子模效用的情况给出了（m-n 1）近似值，对于具有单调效用的最一般模型给出了极端不可估计性结果。
Ivona Bezaacute;kovaacute;, Dani V[6]研究了不可分割商品的分配，分配可分割商品的问题在数学（如切饼问题）和经济学（如市场均衡）中都得到了广泛的关注。另一方面，不可分割商品的自然需求也被忽视了，可能是因为它的性质更为复杂。在这项工作中，他们研究了一个公平标准，称为最大化最小公平分配问题，为K玩家谁想分配自己的不可分割的商品。每个玩家在商品的子集上都有一个特定的估价功能，目的是在玩家之间分割商品，以最大化最小估价。从博弈论的角度来看，对于两个参与者和加性估值，随机切取机制的期望最小值是最优值的1/2近似值。为了补充这一结果，他们表明没有真实的机制能够计算出精确的最优值，当（真）加法估值函数是输入的一部分时，他们也考虑了算法的观点。我们提出一个简单的1/（m-k 1）。
Asadpour A , Saberi A[7]研究了不可分割商品的最大-最小公平分配问题。在设定中，我们将分配M商品给K人。每个人i对于商品j都有一个非负整数的估值uij。假设估值函数是线性的，即对于商品的任何子集C。目标是把每一件商品都分配给一个人，让最不满足的人尽可能满足。更正式地说，希望最大化，其中Ci是分配给个人i的一组商品。对于这个问题，Bansal和Sviri Denko[8]取得了最显著的进展，他们给出了特殊情况下“受限分配”的近似模式，其中，对于所有i，j，我们都有。最近，U. Feige[9]证明了Bansal和Sviri Denko[8]使用的lp的完整性间隙是常数。
Katariacute;na Cechlaacute;rovaacute;, Eva Pillaacute;rovaacute;[10]考虑了公平划分的可计算性。让蛋糕由实际的单位间隔来表示，参与者有由非原子概率度量表示的私有估值。目的是找到一个蛋糕分割法，将一个相邻的块（一个简单的分割法）分配给n个玩家中的每一个，这样每个玩家（通过自己的测量）得到的值对于所有玩家都是相同的，并且这个共同值至少是1/n。众所周知，这种分割法总是存在的，但是，我们表明没有有限的算法可以为三个玩家找到它们。因此，我们提出了一种算法，对于任何给定的εgt;0，在有限的步骤中，找到一个简单的除法，这样分配给参与者的值最多相差εgt;0。
Procaccia A D , Wang J[11]研究了公平分配不可分割商品的问题同时做到最大份额保证。他们考虑公平分配不可分割商品的问题，重点是最近引入的公平概念，即“最大份额保证”：每个玩家的分配价值应至少与他所能保证的一样高，方法是将物品分为尽可能多的捆绑包，然后收到他最不想要的捆绑包。假设加性估值函数，我们表明这种分配可能不存在，但是保证每个参与者2/3以上值的分配总是存在的，并且可以在参与者数量不变的情况下用多项式时间计算。这些理论结果具有直接的现实意义。
D. Kurokawa, A. D. Procaccia, and J. Wang[12]研究最大值共享保证什么时候才能实现？其目标是了解何时我们可以期望给每个玩家提供MMS保证。先前的研究表明，这样的MMS分配可能不存在，但反例需要一些玩家数量呈指数增长的商品；他们给出了一个仅使用线性数量商品的新结构。从积极的方面来说，通过设计一种算法，可以证明当随机抽取估值时，该算法能够找到高概率的MMS分配，从而使这些反例非常微妙的直觉形式化。
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
