A particular Quadratic Transportation Problem
Davide Duma  1, *@  , Stefano Gualandi  1@  , Federico Malucelli  2@  
1 : Università degli Studi di Pavia
2 : Politecnico di Milano
* : Corresponding author

Consider a set of observations consisting of measures on two variables. A statistical test of independence of the two variables is the maximum Pearson's Chi-square index, defined as a Quadratic Transportation Problem (QTP). The QTP is derived from the Linear Transportation Problem: they are both defined on the transportation polytope, but the QTP has an objective function quadratic and convex in the flow variables. Since the solution is one of the many extreme points of the transportation polytope, it is hard to certify the optimality. We introduce a combinatorial relaxation of QTP, and we propose a decomposition method to compute upper bounds, in which the QTP is reduced to 0-1 knapsack problems.

  • Poster
Online user: 2 Privacy