randomized algorithms

Complex Quadratic Optimization and Semidefinite Programming

  • Yongwei Huang
  • Shuzhong Zhang
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , ,

    In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson. We first develop a closed-form formula to compute the probability of … Read more

    Randomized Algorithms for Scene Recognition by Inexact Graph Matching

  • Isabelle Bloch
  • Celso C. Ribeiro
  • Maria Claudia Boeres
    • Categories Biomedical Applications, Graphs and Matroids, Meta Heuristics Tags , , ,

    We propose a new method for non-bijective graph matching for model-based pattern recognition. We formulate the search for the best correspondence between a model and an over-segmented image as a new combinatorial optimization problem, defined by the relational attributed graphs representing the model and the image where recognition has to be performed, together with the … Read more