Simultaneous Optimization via Approximate Majorization for Concave Profits or Convex Costs
Simultaneous Optimization via Approximate Majorization for Concave Profits or Convex Costs
复制标题
通过凹利润或凸成本的近似多数化同时优化
DOI：
10.1007/s00453-005-1177-7
复制
发表时间：
2006
期刊：
影响因子：
1.1
通讯作者：
A. Meyerson
中科院分区：
文献类型：
--
作者：
Ashish Goel;A. Meyerson
摘要
对于多准则问题以及目标特征不明确的问题，通常希望同时近似一大类目标函数的最优解。我们考虑两类这样的函数：（1）最大化所有对称凹函数。（2）最小化所有对称凸函数。第一类对应于资源分配问题（例如计算机网络中带宽的分配）中的利润最大化。凹性要求对应于经济学中的收益递减规律。第二类对应于负载均衡问题中的成本或拥塞最小化，其中拥塞/成本是负载的某个凸函数。通俗地说，对于任一类函数，同时的α -近似是一个可行解，对于该类中的所有函数，它与最优解的差距在α因子范围内。显然，可行集的结构对最佳可能的α以及找到达到（或接近达到）此α的解的计算复杂度有重大影响。我们开发了一个框架和一套技术，用于对各种各样的问题进行同时优化。
我们首先将两类函数的同时α -近似与α -近似优超相关联。然后我们证明，对于凹利润情况，当α取对数时，存在α -近似优超的解。对于这两类函数，如果约束集是一个多项式规模的线性规划，我们提出一个多项式时间算法来找到最佳的α，并讨论了几个非平凡的应用。这些应用包括为多商品流找到一个（log n）-优超解，以及为各种形式的负载均衡问题找到近似最佳的α。我们的技术也可应用于产生设施选址和双准则网络设计问题的近似公平版本。此外，我们展示了分布式负载均衡（其中作业的大小是从已知概率分布中抽取的，但在放置时实际大小未知）与近似优超之间有趣的联系。
AbstractFor multicriteria problems and problems with a poorly
characterized objective, it is often desirable to approximate simultaneously
the optimum solution for a large class of objective functions.
We consider two such classes: (1) Maximizing all symmetric concave functions.
(2) Minimizing all symmetric convex functions. The first class corresponds to maximizing profit for a resource allocation
problem (such as allocation of bandwidths in a computer network). The
concavity requirement corresponds to the law of diminishing returns in
economics. The second class corresponds to minimizing cost or congestion
in a load balancing problem, where the congestion/cost is some convex
function of the loads. Informally, a simultaneous α-approximation for either class is a
feasible solution that is within a factor α of the optimum for all
functions in that class. Clearly, the structure of the feasible set has a
significant impact on the best possible α and the computational
complexity of finding a solution that achieves (or nearly achieves) this
α. We develop a framework and a set of techniques to perform
simultaneous optimization for a wide variety of problems. We first relate simultaneous α-approximation for both classes to
α-approximate majorization. Then we prove that
α-approximately majorized solutions exist for logarithmic values of
α for the concave profits case. For both classes, we present a
polynomial-time algorithm to find the best α if the set of
constraints is a polynomial-sized linear program and discuss several
non-trivial applications. These applications include finding a (log
n)-majorized solution for multicommodity flow, and finding approximately
best α for various forms of load balancing problems. Our
techniques can also be applied to produce approximately fair versions of
the facility location and bi-criteria network design problems. In
addition, we demonstrate interesting connections between distributional
load balancing (where the sizes of jobs are drawn from known probability
distributions but the actual size is not known at the time of placement)
and approximate majorization.