论文部分内容阅读
资源分配问题在经济、管理等许多领域都占有非常重要的地位。如何充分利用有限的资源以最大化利润(Revenue)或者社会效益(Social Welfare)一直以来都是各个领域的资源提供者们共同关心的问题。随着互联网的兴起，资源分配问题变得更加复杂:资源的需求情况越来越难以预测。例如，在云计算、在线广告、在线租赁等新兴互联网市场中，资源请求可以认为是以某种顺序一个接一个到来的，未观察到的请求是难以预测的。对每一个到来的请求，资源提供者需要根据目前掌握的局部信息快速做出响应，这些响应通常是不可逆的。在这种情况下，如何在当前面临的低收益请求和潜在的不可预知的高收益请求之间做取舍是一个非常困难的问题。 为了解决这个问题，在线算法(Online Algorithm)的概念被提了出来，并且受到了越来越多学者的关注。事实上，在线算法不仅局限于资源分配问题，它同样适用于商品动态定价、股票交易等问题。正是在线算法的广泛应用性，使其成为理论计算机领域的热门方向，近些年来有大量的相关工作。 在不同的应用场景中，资源的属性和分配规则具有本质的不同。本文集中研究了三种典型的在线资源分配问题，针对它们建立模型并提出了具有理论保证的资源分配算法。本文主要有以下贡献: 1.研究了并行多选择秘书问题（Parallel Multi-Choice Secretary Problem）。在该问题中，雇主需要雇佣多名秘书，一定数量的候选人以均匀随机的顺序到来。出于时间等限制，这些候选人被分配到多个队列并行面试。雇主的目的是要雇佣到最好的一批候选人。可以看到，该问题本质上是一个单类资源的分配问题，其中雇佣名额对应资源，候选人对应请求。本文首先使用线性规划(Linear Programming)技术，对一般情况下的并行多选择秘书问题建立线性规划模型，然后通过对该线性规划及其对偶问题最优解结构的深入研究，设计出一个确定性的最优算法。相较于线性规划最优解直接变换得到的随机算法，本文提出的算法更加简单、易于实现，并且构造算法的时间复杂度要远优于用传统方法解对应的线性规划; 2.研究了在线带权二部图匹配问题(Online Weighted Bipartite Matching Problem)。该问题是单类资源分配问题在资源类型上的推广。在该问题中，资源提供者有多类资源，表示为二部图中离线已知的左边点集;一系列的资源请求以在线的方式一个接一个的到来，这些请求表示为在线到来的右边点集。每到来一个请求，它可以连接的资源以及对应的价值才会展示出来。资源提供者需要立即对每一个请求做出响应:是否接受这个请求以及在接受的情况下，应该把哪个资源分配给它。当所有的请求到来之后，提供者以在线的方式构造了一个匹配，而优化目标正是最大化该匹配的权重和。本文首先证明了当权重任意时，不存在高效的资源分配算法，然后本文提出了两种权重受限的新模型，并设计了解决这两个模型的近似算法。通过姚氏最小-最大定理，本文证明这些算法是近似最优的; 3.研究了在线可复用资源预订问题(Online Reservation Problem for Reusable Resources)。该问题是单类资源分配问题在时间维度上的扩展。在该问题中，资源提供者有多个相同的可复用资源，例如云计算中的虚拟机、租赁市场中的房屋等。这些资源以预定的方式进行分配。当每个预订请求到来之后，资源提供者会看到该预订的参数，例如起止时间、需要的资源数量等，并且需要决定是否满足该预订请求以及如何分配资源并收费。根据角色的不同，提供者的目的是最大化社会效益（所有接受的预订的价值和）或利润（所有接受的预订的收费总和）。本文考虑了对手模型(Adversarial Model)和随机模型(Stochastic Model)两种预订到来模型。在对手模型中，预订到来的顺序与参数都是由一个熟悉分配算法的对手设置的。资源提供者对于未来的预订信息一无所知。在这个模型下，本文提出的算法取得了远好于已有算法的性能。在随机模型中，本文首次将随机信息引入在线资源预订问题，即每个预订的一些参数是服从某个已知分布的，在这个情况下，本文证明仅使用少量的分布信息即可取得远超对手模型的效果。 上述三种资源分配问题具有很强的内在关联。在并行多选择秘书问题中，资源提供者只有一类资源，所有的请求都在竞争这些资源。其本质上是一个单类资源的分配问题。当资源的种类增多时，不同的请求竞争不同的资源，而同一资源对于不同请求价值也不一样，其组合结构变得更复杂。这个问题即是在线带权二部图匹配问题，其本质是一个多类单个资源的分配问题。同样还可以在时间维度上扩展单类资源分配问题，即用户并非是独占某个资源的，而是仅在特定时间段使用资源。这就得到了在线可复用资源预订问题。 除了上述贡献，本文的工作在理论上扩展了对在线问题进行建模和分析的方法。首先，本文在并行多选择问题的研究中使用了线性规划技术，扩展了该技术在在线算法领域的应用，为其他在线算法研究提供了重要参考。其次，在多个资源分配问题的算法上界分析中，本文都用到了姚氏最小-最大定理，其中构造输入分布的一些技巧对其他在线问题的分析具有借鉴价值。最后，通过将随机信息引入可复用资源的分配，并且同对手模型进行对比，本文展示了数据及其背后的蕴含的信息对于解决在线问题的重要性。这一点在“大数据时代”尤为重要，它引发我们对于数据与理论算法研究之间关系的思考，促使我们从数据中获取更多信息，去解决之前难以解决的问题。