Abstrakt. Författarna presenterar en O(inn log m) algoritm för att lösa genomförbarhet i linjära program med upp till två variabler per ojämlikhet som härleds direkt från Fourier-Motzkin elimineringsmetoden. (Antalet variabler och ojämlikheter betecknas med n respektive m.) Körtiden för algoritmen dominerar den mest kända algoritmen för problemet, och är mycket enklare. Integerprogrammering om monotona ojämlikheter, dvs. ojämlikheter där koefficienterna är av motsatt tecken, beaktas sedan. Detta problem omfattar som specialfall samtidig approximation av en rationell vektor med specificerad noggrannhet, som är känd för att vara NP-komplett. Det visas dock att både en genomförbar lösning och en optimal lösning med avseende på en godtycklig objektiv funktion kan beräknas i pseudo-polynom tid.
I REF användes Fourier-Motzkin elimineringsproceduren för att ge en starkt polynomal algoritm, som hittills är den snabbaste kända algoritmen för detta problem.
Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}