linearization problem

The Quadratic Cycle Cover Problem: special cases and efficient bounds

  • Frank de Meijer
  • Renata Sotirov
    • Categories Combinatorial Optimization Tags , , ,

    The quadratic cycle cover problem is the problem of finding a set of node-disjoint cycles visiting all the nodes such that the total sum of interaction costs between incident arcs is minimized. In this paper we study the linearization problem for the quadratic cycle cover problem and related lower bounds. In particular, we derive various … Read more

    A polynomial time algorithm for the linearization problem of the QSPP and its applications

  • Hao Hu
  • Renata Sotirov
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    Given an instance of the quadratic shortest path problem (QSPP) on a digraph $G$, the linearization problem for the QSPP asks whether there exists an instance of the linear shortest path problem on $G$ such that the associated costs for both problems are equal for every $s$-$t$ path in $G$. We prove here that the … Read more