Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems

摘要

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.