Month: April 2011

Efficient Solutions for the Far From Most String Problem

  • Paola Festa
  • Panos M. Pardalos
    • Categories Basic Sciences Applications, Combinatorial Optimization, Meta Heuristics Tags , , , ,

    Computational molecular biology has emerged as one of the most exciting interdisciplinary fields. It has currently benefited from concepts and theoretical results obtained by different scientific research communities, including genetics, biochemistry, and computer science. In the past few years it has been shown that a large number of molecular biology problems can be formulated as … Read more

    Approximation algorithms for trilinear optimization with nonconvex constraints and its extensions

  • Yuning Yang
  • Qingzhi Yang
    • Categories Semi-definite Programming Tags , , , ,

    In this paper, we study trilinear optimization problems with nonconvex constraints under some assumptions. We first consider the semidefinite relaxation (SDR) of the original problem. Then motivated by So \cite{So2010}, we reduce the problem to that of determining the $L_2$-diameters of certain convex bodies, which can be approximately solved in deterministic polynomial-time. After the relaxed … Read more