Artur Alves Pessoa

An Approximation Algorithm for Constructing Error Detecting Prefix Codes

  • Artur Alves Pessoa
    • Categories Approximation Algorithms, Telecommunications Tags , ,

    A $k$-bit Hamming prefix code is a binary code with the following property: for any codeword $x$ and any prefix $y$ of another codeword, both $x$ and $y$ having the same length, the Hamming distance between $x$ and $y$ is at least $k$. Given an alphabet $A = [a_1,\ldots,a_n]$ with corresponding probabilities $[p_1,\ldots,p_n]$, the $k$-bit … Read more

    Robust Branch-Cut-and-Price for the Capacitated Minimum Spanning Tree Problem over a Large Extended Formulation

  • Diogo V. Andrade
  • Ricardo Fukasawa
  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
  • Jens Lysgaard
    • Categories Cutting Plane Approaches Tags , ,

    This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to $q$-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arborescence probem in order to make it solvable in pseudo-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. … Read more