Algoritmi di Las Vegas per Programmi Lineari di dimensione piccola

Vengono analizzati tre articoli scritti da N. Megiddo, K. Clarkson, R. Seidel che propongono algoritmi che abbiano costo lineare nel numero di vincoli di un Programma Lineare quando la dimensione di tale programma è piccola (fissata o cresce molto lentamente rispetto al numero di vincoli). In particolare gli ultimi due autori propongono di effettuare una scelta randomica all'interno dell'algoritmo, che migliorerà molto la dipendenza dalla dimensione del PL nel valore atteso del costo computazionale rispetto al metodo di Megiddo; tali algoritmi in cui è presente una componente aleatoria, che raggiungono l'ottimo del PL in un tempo atteso lineare nel numero di vincoli, prendono il nome di Algoritmi di Las Vegas.