Vi ger en exakt algoritm för 0-1 Integer Linear Programmering problem med ett linjärt antal begränsningar som förbättrar över uttömmande sökning med en exponentiell faktor. Specifikt, vår algoritm körs i tid 2 (1-poly(1/c)n där n är antalet variabler och cn är antalet begränsningar. Den viktigaste idén för algoritmen är en minskning till Vector Domination problem och en ny algoritm för att subproblem.
Impagliazzo m.fl. lösa 0-1 ILP genomförbarhet problem med exponentiellt påskynda över uttömmande sökning i specialfall där antalet begränsningar är en multipel av antalet variabler; Detta uppnås genom en minskning till vektor dominans problem REF.
0-1 Integer Linear Programming with a Linear Number of Constraints
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}