Linear discrepancy search for small BvN decompositions

Abstract

The Birkhoff-von Neumann (BvN) decomposition, which expresses a doubly stochastic matrix as a convex combination of permutation matrices, is a fundamental problem in combinatorial optimization. Finding a decomposition with the minimum number of permutation matrices is NP-hard, leading to the widespread use of heuristics. The stateof-the-art greedy heuristic, which maximizes the bottleneck value at each step, is efficient but may become trapped in local optima. This work investigates the application of Limited Discrepancy Search (LDS) as a meta-heuristic to improve upon the greedy approach. By allowing a limited number of controlled deviations from the greedy choice, LDS explores a broader region of the solution space to potentially find shorter decompositions. We present a theoretical complexity analysis of the LDS-based algorithm and conduct experiments on both sparse real-world matrices and randomly generated dense matrices. The results demonstrate that LDS often finds decompositions that are of equal or superior quality to those produced by the greedy heuristic. The analysis of performance scaling, solution quality, and discrepancy patterns confirms that LDS is a practical method for attempting to escape local optima and refining BvN decompositions, albeit at an increased computational cost.

Adecomposição de Birkhoff-von Neumann (BvN), que expressa uma matriz duplamente estocástica como uma combinação convexa de matrizes de permutação, é um problema fundamental em otimização combinatória. Encontrar uma decomposição com o número mínimo de matrizes de permutação é um problema NP-difícil, levando ao uso generalizado de heurísticas. A heurística gulosa, que constitui o estado da arte e maximiza o valor gargalo a cada passo, é eficiente, mas pode ficar presa em ótimos locais. Este trabalho investiga a aplicação da Busca por Discrepância Limitada (LDS) como uma meta-heurística para aprimorar a abordagem gulosa. Ao permitir um número limitado de desvios controlados da escolha gulosa, a LDS explora uma região mais ampla do espaço de soluções para potencialmente encontrar decomposições mais curtas. Apresentamos uma análise de complexidade teórica do algoritmo baseado em LDS e realizamos experimentos tanto em matrizes esparsas do mundo real quanto em matrizes densas geradas aleatoriamente. Os resultados demonstram que a LDS frequentemente encontra decomposições de qualidade igual ou superior àquelas produzidas pela heurística gulosa. A análise de escalabilidade de desempenho, qualidade da solução e padrões de discrepância confirma que a LDS é um método prático para tentar escapar de ótimos locais e refinar as decomposições de BvN, embora com um custo computacional maior.