BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/490
DTSTAMP:20230914T125926Z
SUMMARY:Sparse Process Flexibility Designs: Is Long-Chain Really Optimal?
DESCRIPTION:Speaker: Vineet Goyal (Columbia University\nIndustrial Engineer
ing and Operations Research\n500 West\, 120th Street\nNew York\, NY 10027\
nUnited States of America)\n\nAbstract: \nAbstract: Long chain refers to a
directed bi-partite network with directed edges from supply nodes (with f
ixed unit supply) to demand nodes (with random demand) that form a hamilto
nian cycle. This design was introduced in a seminal paper of Jordan and Gr
aves (1995) and has been an important design in process flexibility. Jord
an and Graves (1995) observed empirically that the expected performance (s
atisfied demand) is quite close to the complete bi-partite graph for certa
in demand distributions. Recently\, Simchi-Levi and Wei (2012) show that l
ong chain maximizes the expected performance among all 2-regular networks
for exchangeable demand distributions.\n\nWe study the performance of long
chain in comparison to all networks with 2n edges when the assumption of
2-regularity is relaxed. We show that surprisingly long chain is not optim
al in this class of networks even for i.i.d. demand distributions. We pres
ent a family of instances where a disconnected network with 2n edges has a
strictly better performance than long chain.\n\nHowever\, if we restrict
to connected networks with 2n arcs\, we show that long chain is optimal f
or exchangeable demand distributions. Our proof is based on a combinatoria
l analysis of the structure of maximum flow in directed graphs and a coupl
ing argument that reduces the comparison of expected performance to a samp
le pathwise comparison of satisfied demand. Our analysis provides useful i
nsights towards not just understanding the optimality of long chain but al
so towards designing more general sparse flexibility networks (this is joi
nt work with Antoine Desir\, Yehua Wei and Jiawei Zhang).\n \n
URL:https://www.tcs.tifr.res.in/web/events/490
DTSTART;TZID=Asia/Kolkata:20140522T160000
DTEND;TZID=Asia/Kolkata:20140522T170000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR