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.

U-curve: A branch-and-bound optimization algorithm for U-shaped cost functions on Boolean lattices applied to the feature selection problem

This paper presents the formulation of a combinatorial optimization problem with the following characteristics: (i) the search space is the power set of a finite set structured as a Boolean lattice; (ii) the cost function forms a U-shaped curve when applied to any lattice chain. This formulation applies for feature selection in the context of pattern recognition. The known approaches for this problem are branch-and-bound algorithms and heuristics that explore partially the search space. Branch-and-bound algorithms are equivalent to the full search, while heuristics are not. This paper presents a branch-and-bound algorithm that differs from the others known by exploring the lattice structure and the U-shaped chain curves of the search space. The main contribution of this paper is the architecture of this algorithm that is based on the representation and exploration of the search space by new lattice properties proven here. Several experiments, with well known public data, indicate the superiority of the proposed method to the sequential floating forward selection (SFFS), which is a popular heuristic that gives good results in very short computational time. In all experiments, the proposed method got better or equal results in similar or even smaller computational time. (C) 2009 Elsevier Ltd. All rights reserved.

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

A Bayesian Semiparametric Approach for Solving the Discrete Calibration Problem

In this article, we introduce a semi-parametric Bayesian approach based on Dirichlet process priors for the discrete calibration problem in binomial regression models. An interesting topic is the dosimetry problem related to the dose-response model. A hierarchical formulation is provided so that a Markov chain Monte Carlo approach is developed. The methodology is applied to simulated and real data.

ON AMINO ACID AND CODON ASSIGNMENT IN ALGEBRAIC MODELS FOR THE GENETIC CODE

We give a list of all possible schemes for performing amino acid and codon assignments in algebraic models for the genetic code, which are consistent with a few simple symmetry principles, in accordance with the spirit of the algebraic approach to the evolution of the genetic code proposed by Hornos and Hornos. Our results are complete in the sense of covering all the algebraic models that arise within this approach, whether based on Lie groups/Lie algebras, on Lie superalgebras or on finite groups.

ON THE SUPERCRITICALITY OF THE FIRST HOPF BIFURCATION IN A DELAY BOUNDARY PROBLEM

The goal of this paper is to analyze the character of the first Hopf bifurcation (subcritical versus supercritical) that appears in a one-dimensional reaction-diffusion equation with nonlinear boundary conditions of logistic type with delay. We showed in the previous work [Arrieta et al., 2010] that if the delay is small, the unique non-negative equilibrium solution is asymptotically stable. We also showed that, as the delay increases and crosses certain critical value, this equilibrium becomes unstable and undergoes a Hopf bifurcation. This bifurcation is the first one of a cascade occurring as the delay goes to infinity. The structure of this cascade will depend on the parameters appearing in the equation. In this paper, we show that the first bifurcation that occurs is supercritical, that is, when the parameter is bigger than the delay bifurcation value, stable periodic orbits branch off from the constant equilibrium.

An eigenvalue problem for the biharmonic operator on Z(2)-symmetric regions

In this work we show that the eigenvalues of the Dirichlet problem for the biharmonic operator are generically simple in the set Of Z(2)-symmetric regions of R-n, n >= 2, with a suitable topology. To accomplish this, we combine Baire`s lemma, a generalised version of the transversality theorem, due to Henry [Perturbation of the boundary in boundary value problems of PDEs, London Mathematical Society Lecture Note Series 318 (Cambridge University Press, 2005)], and the method of rapidly oscillating functions developed in [A. L. Pereira and M. C. Pereira, Mat. Contemp. 27 (2004) 225-241].

Bjorling problem for timelike surfaces in the Lorentz-Minkowski space

We solve the Bjorling problem for timelike surfaces in the Lorentz-Minkowski space through a split-complex representation formula obtained for this kind of surface. Our approach uses the split-complex numbers and natural split-holomorphic extensions. As applications, we show that the minimal timelike surfaces of revolution as well as minimal ruled timelike surfaces can be characterized as solutions of certain adequate Bjorling problems in the Lorentz-Minkowski space. (C) 2010 Elsevier Inc. All rights reserved.

Decomposability problem on branched coverings

Given a branched covering of degree d between closed surfaces, it determines a collection of partitions of d, the branch data. In this work we show that any branch data are realized by an indecomposable primitive branched covering on a connected closed surface N with chi(N) <= 0. This shows that decomposable and indecomposable realizations may coexist. Moreover, we characterize the branch data of a decomposable primitive branched covering. Bibliography: 20 titles.

A FREE BOUNDARY ISOPERIMETRIC PROBLEM IN HYPERBOLIC 3-SPACE BETWEEN PARALLEL HOROSPHERES

We investigate the isoperimetric problem of finding the regions of prescribed volume with minimal boundary area between two parallel horospheres in hyperbolic 3-space (the part of the boundary contained in the horospheres is not included). We reduce the problem to the study of rotationally invariant regions and obtain the possible isoperimetric solutions by studying the behavior of the profile curves of the rotational surfaces with constant mean curvature in hyperbolic 3-space. We also classify all the connected compact rotational surfaces M of constant mean curvature that are contained in the region between two horospheres, have boundary partial derivative M either empty or lying on the horospheres, and meet the horospheres perpendicularly along their boundary.

New classes of spatial central configurations for the n+3-body problem

In this paper, we show the existence of new families of spatial central configurations for the n + 3-body problem, n >= 3. We study spatial central configurations where n bodies are at the vertices of a regular n-gon T and the other three bodies are symmetrically located on the straight line that is perpendicular to the plane that contains T and passes through the center of T. The results have simple and analytic proofs. (c) 2010 Elsevier Ltd. All rights reserved.

Stacked central configurations for the spatial six-body problem

In this paper we show the existence of three new families of stacked spatial central configurations for the six-body problem with the following properties: four bodies are at the vertices of a regular tetrahedron and the other two bodies are on a line connecting one vertex of the tetrahedron with the center of the opposite face. (c) 2009 Elsevier B.V. All rights reserved.

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.

Complete assignment of (1)H and (13)C NMR spectra of alpha-phenylsulfinyl-N-methoxy-N-methylpropionamide and some p-substituted derivatives

The complete assignment of the (1)H and (13)C NMR spectra of the diastereomeric pairs of some alpha-arylsulfinyl-substituted N-methoxy-N-methylpropionamides with the substituents methoxy, methyl, chloro, nitro is reported. Copyright (C) 2008 John Wiley & Sons, Ltd.