Corrispondenza multipla nel problema del flusso massimo?

Question

Mi dispiace se questo è già stato chiesto prima, ma non sono riuscito a trovare domande simili. La situazione è come tale:

Supponiamo che ci siano x ristoranti, ognuno con una capacità Q e Y, ognuna delle quali può mangiare solo da un ristorante. I ristoranti X possono servire le persone solo a raggio R dalla sua posizione. Prova a trovare il numero massimo di persone che possono essere servite da un ristorante e da quale ristorante deve mangiare ognuno.

Il mio approccio era di dividerlo in qualcosa di simile al problema della corrispondenza bipartita. Avere i ristoranti X da un lato e persone dall'altra. Quindi, avrei un nodo iniziale che si collega a ogni ristorante utilizzando un bordo diretto della capacità q. Quindi, collegherei tutte le persone Y con un bordo diretto della capacità 1 a un nodo lavandino, t. Infine, collegherei tutti i ristoranti a tutte le persone nel raggio R usando un bordo diretto della capacità 1.

Gestire l'algoritmo Ford-Fulkerson su questo, tuttavia, potrebbe provocare un ristorante che serve meno di quanto potessero potenzialmente (ad esempio, supponiamo che abbiamo due ristoranti ciascuno con capacità 2, 4 persone e il primo ristorante si collega alle prime tre persone E il secondo si collega agli ultimi due; quindi, se il percorso dal primo ristorante al terzo è aumentato nell'algoritmo, possiamo solo servire 3 persone anziché un ottimale di 4). La mia soluzione alternativa è forse aumentare un percorso ST con il minor numero di bordi in arrivo alla persona (quindi una situazione come quanto sopra può essere evitata), ma questo chiaramente rallenta l'efficienza significativamente dell'algoritmo, oltre a renderlo molto Più difficile fornire un argomento dicendo che è ottimale.

Esiste una letteratura su problemi come questi o qualche suggerimento su come posso migliorare il mio approccio? Grazie!