Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
复制标题
DOI：
10.1016/j.dam.2013.03.001
复制
发表时间：
2013-09
期刊：
影响因子：
--
通讯作者：
A. V. Zuylen
中科院分区：
文献类型：
--
作者：
A. V. Zuylen
我们给去随机化已知的随机近似算法的最大旅行商问题和最大三角包装问题：我们展示了如何定义悲观估计某些概率的基础上分析的随机算法，并表明，我们可以乘估计，以获得悲观估计的预期权重的解决方案。悲观估计方法（Raghavan（1988）[14]）则直接意味着随机化算法可以去随机化。对于最大三角形填充问题，这给出了比以前已知的更好的近似保证的确定性算法。我们分析的关键思想是两个期望E[Y]和E[Z]的悲观估计的条件的规定，在此条件下，悲观估计的乘积是E[YZ]的悲观估计，其中Y和Z是两个随机变量。这种方法可以是有用的去随机化算法时，需要绑定的概率，可以表示为多个事件的交集的一些事件;使用我们的方法，可以定义悲观估计的概率的个别事件，然后将它们相乘，以获得一个悲观估计的概率的交集的事件。
We give derandomizations of known randomized approximation algorithms for the maximum traveling salesman problem and the maximum triangle packing problem: we show how to define pessimistic estimators for certain probabilities, based on the analysis of the randomized algorithms, and show that we can multiply the estimators to obtain pessimistic estimators for the expected weight of the solution. The method of pessimistic estimators (Raghavan (1988) [14]) then immediately implies that the randomized algorithms can be derandomized. For the maximum triangle packing problem, this gives deterministic algorithms with better approximation guarantees than what was previously known. The key idea in our analysis is the specification of conditions on pessimistic estimators of two expectations E[Y] and E[Z], under which the product of the pessimistic estimators is a pessimistic estimator of E[YZ], where Y and Z are two random variables. This approach can be useful when derandomizing algorithms for which one needs to bound the probability of some event that can be expressed as an intersection of multiple events; using our method, one can define pessimistic estimators for the probabilities of the individual events, and then multiply them to obtain a pessimistic estimator for the probability of the intersection of the events.