Multiple correspondant dans un problème d'écoulement maximal?

Question

Je suis désolé si cela a déjà été demandé auparavant, mais je n'ai pas trouvé de questions similaires. La situation est en tant que telle:

Supposons qu'il y ait X restaurants, chacun avec une capacité Q, et des personnes, chacune ne peut manger que dans un seul restaurant. Les X restaurants ne peuvent servir que les gens dans le rayon R de son emplacement. Essayez de trouver le nombre maximum de personnes qui peuvent être desservies par un restaurant et quel restaurant chacun doit manger.

Mon approche était de le diviser en quelque chose de similaire au problème de correspondance bipartite. Ayez les restaurants X d'un côté et les gens de l'autre. Ensuite, j'aurais un nœud de démarrage qui se connecte à chaque restaurant en utilisant un bord de capacité dirigé Q. Ensuite, je connecterais toutes les personnes Y avec un bord de capacité dirigé 1 à un nœud d'évier, t. Enfin, je connecterais tous les restaurants à toutes les personnes de Radius R en utilisant un bord de capacité dirigé 1.

La gestion de l'algorithme Ford-Fulkerson à ce sujet pourrait cependant entraîner un restaurant moins que possible (par exemple, disons que nous avons deux restaurants chacun avec une capacité 2, 4 personnes, et le premier restaurant se connecte aux trois premières personnes Et le second se connecte aux deux derniers; alors, si le chemin du premier restaurant au troisième est augmenté dans l'algorithme, nous ne pouvons servir que 3 personnes au lieu d'un optimum de 4). Ma solution de contournement est peut-être peut-être augmenter un chemin ST avec le moins de bords entrants à la personne (donc une situation comme ce qui précède peut être évitée), mais cela ralentit clairement l'efficacité considérablement de l'algorithme, tout en le faisant beaucoup Plus difficile de fournir un argument disant que c'est optimal.

Y a-t-il une littérature concernant des problèmes comme ceux-ci, ou des suggestions sur la façon dont je peux améliorer mon approche? Merci!