סילבוס

תוכן הקורס ומטרתו

0512.4009 אלגוריתמים ברשתות
משקל: 4
דרישות קדם: תכנון וניתוח אלגוריתמים

הקורס מתמקד בנושאים מתקדמים של אלגוריתמים ברשתות. נושאים שיכוסו בקורס כוללים בין היתר תכנון לינארי ואלגוריתמים לבעיות יסודיות בגרפים, כולל זרימה מקסימלית וזרימה במחיר מינימלי, חתך מינימלי, זיווג בגרף, קשירות, ועוד.

ספרות רלוונטית:
Cook, W.J., Cunningham, W., Pulleyblank, W. and Schrijver, A., 2009. Combinatorial optimization. Oberwolfach Reports, 5(4), pp.2875-2942.

Goldberg, A.V., 1991. Combinatorial Optimization (Lecture Notes).

Goldberg, A.V. and Tarjan, R.E., 1988. A new approach to the maximum-flow problem. Journal of the ACM (JACM), 35(4), pp.921-940.

Goldberg, A.V. and Tarjan, R.E., 1989. Finding minimum-cost circulations by canceling negative cycles. Journal of the ACM (JACM), 36(4), pp.873-886.

Ahuja, R.K., Magnanti, T.L., Orlin, J.B. and Weihe, K., 1995. Network flows: theory, algorithms and applications. ZOR-Methods and Models of Operations Research, 41(3), pp.252-254.

Bertsimas, D. and Tsitsiklis, J.N., 1997. Introduction to linear optimization (Vol. 6, pp. 479-530). Belmont, MA: Athena Scientific.

Papadimitriou, C.H. and Steiglitz, K., 1998. Combinatorial optimization: algorithms and complexity. Courier Corporation.

Even, S., 2011. Graph algorithms. Cambridge University Press.