Leírás
Az előadásban Kazuo Murotával közösen végzett
vizsgálataink második részéről adok áttekintést. A
korábbiakban egy bázis-poliéder egész pontjaiból álló
halmaznak (magyarul M-konvex halmaznak) kerestünk egy z
csökkenően minimális elemét, ami azt jelenti, hogy a
legnagyobb $z$-komponens a lehető legkisebb, ezen belül a
második legnagyobb (nem feltétlenül különböző
értékű) $z$-komponens a lehető legkisebb, és így
tovább. A mostani előadás fő célja egy csökkenően
minimális egész-értékű $(f,g)$-megengedett áram
meghatározására szolgáló algoritmus bemutatása.
Bebizonyítjuk, hogy az $(f,g)$ alsó-felső korlátnak
létezik egy olyan $(f^*,g^*)$ szűkítése ($f\leq f^* \leq g^* \leq g$), amelyre érvényes, hogy az
egész-értékű $(f^*,g^*)$-megengedett áramok
alkotják a csökkenően minimális egész-értékű
$(f,g)$-megengedett áramokat. Ráadásul az $(f^*,g^*)$
pár keskeny abban az értelemben, hogy
$0\leq g^*(e)- f^*(e)\leq 1$ fennáll minden e élre.