Vi beskriver sekventiella och parallella algoritmer som ungefär löser linjära program utan negativa koefficienter (alias. Blandade förpacknings- och täckproblem). För uttryckligen givna problem, vår snabbaste sekventiella algoritm returnerar en lösning som uppfyller alla begränsningar inom en 1 ±  på en faktor i O (md log(m)/ på 2 ) tid, där m är antalet begränsningar och d är det maximala antalet begränsningar någon variabel visas i. Det viktigaste bidraget är att algoritmerna löser problem med blandad packning och täckning (till skillnad från problem med ren packning eller ren beläggning, som bara har "≤" eller bara " på" ojämlikheter, men inte båda) och körs i tid oberoende av den så kallade bredden av problemet.
För uttryckligen angivna packning och täckning, den snabbaste tidigare Lagrangian-relaxation algoritm som vi känner till körningar i tid O(r + c)c log(n) /ε 2 ), varc är det maximala antalet kolumner där någon variabel visas REF.
Sequential and Parallel Algorithms for Mixed Packing and Covering
{'venue': 'IEEE Symposium on Foundations of Computer Science (2001)', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}