Agregando información inconsistente

Abordamos problemas de optimización en los que se nos dan piezas contradictorias de información de entrada y el objetivo es encontrar una solución globalmente consistente que minimice la extensión del desacuerdo con las respectivas entradas. Específicamente, los problemas que abordamos son la agregación de rangos, el problema del conjunto de arcos de retroalimentación en torneos y el agrupamiento de correlación y consenso. Mostramos que para todos estos problemas (y varias versiones ponderadas de ellos), podemos obtener factores de aproximación mejorados utilizando esencialmente el mismo algoritmo notablemente simple. Adicionalmente, casi resolvemos una conjetura duradera de Bang-Jensen y Thomassen y mostramos que a menos que NP⊆BPP, no hay un algoritmo en tiempo polinómico para el problema del mínimo conjunto de arcos de retroalimentación en torneos.