Approximating a class of combinatorial problems with rational objective function

In the late seventies, Megiddo proposed a way to use an algorithm for the problem of minimizing a linear function a(0) + a(1)x(1) + ... + a(n)x(n) subject to certain constraints to solve the problem of minimizing a rational function of the form (a(0) + a(1)x(1) + ... + a(n)x(n))/(b(0) + b(1)x(1) + ... + b(n)x(n)) subject to the same set of constraints, assuming that the denominator is always positive. Using a rather strong assumption, Hashizume et al. extended Megiddo`s result to include approximation algorithms. Their assumption essentially asks for the existence of good approximation algorithms for optimization problems with possibly negative coefficients in the (linear) objective function, which is rather unusual for most combinatorial problems. In this paper, we present an alternative extension of Megiddo`s result for approximations that avoids this issue and applies to a large class of optimization problems. Specifically, we show that, if there is an alpha-approximation for the problem of minimizing a nonnegative linear function subject to constraints satisfying a certain increasing property then there is an alpha-approximation (1 1/alpha-approximation) for the problem of minimizing (maximizing) a nonnegative rational function subject to the same constraints. Our framework applies to covering problems and network design problems, among others.

Resolution and Absolute Configuration Assignment of a Natural Racemic Chromane from Peperomia obtusifolia (Piperaceae)

The resolution of the natural racemic chromane 3,4-dihydro-5-hydroxy-2,7-dimethyl-8-(3 ``-methyl-2 ``-butenyl)-2-(4`-methyl-1`,3`-pentadienyl)-2H-1-benzopyran-6-carboxylic acid (1) isolated from the leaves of Peperomia obtusifolia has been accomplished using stereoselective HPLC. The absolute coil figuration of the resolved enantiomers was determined by the analysis of optical rotations and CD spectra. The finding of a racemic mixture instead of an enantiomerically pure metabolite raises questions about the final steps in the biosynthesis of this class of natural products, suggesting that the intramolecular chromane ring formation step may not be enzymatically controlled at all in P. obtusifolia. Chirality 21:799-801, 2009. (C) 2008 Wiley-Liss, Inc.