Note: This is an archived Handbook entry from 2016.
|Dates & Locations:|| |
This subject is not offered in 2016.
|Time Commitment:||Contact Hours: 36 hours comprising one 2-hour lecture per week and one 1-hour practice class per week. |
Total Time Commitment:
The following subject, or equivalent:
Study Period Commencement:
|Recommended Background Knowledge:|| |
An introductory-level subject in operations research equivalent to
Study Period Commencement:
|Non Allowed Subjects:||None|
|Core Participation Requirements:||
For the purposes of considering request for Reasonable Adjustments under the Disability Standards for Education (Cwth 2005), and Student Support and Engagement Policy, academic requirements for this subject are articulated in the Subject Overview, Learning Outcomes, Assessment and Generic Skills sections of this entry.
It is University policy to take all reasonable steps to minimise the impact of disability upon academic study, and reasonable adjustments will be made to enhance a student's participation in the University's programs. Students who feel their disability may impact on meeting the requirements of this subject are encouraged to discuss this matter with a Faculty Student Adviser and Student Equity and Disability Support: http://services.unimelb.edu.au/disability
Many practical problems in management, operations research, telecommunication and computer networking can be modelled as optimisation problems on networks. Here the underlying structure is a graph. This subject is an introduction to optimisation problems on networks with a focus on theoretical results and efficient algorithms. It covers classical problems that can be solved in polynomial time, such as shortest paths, maximum matchings, maximum flows, and minimum cost flows. Other topics include complexity and NP-completeness, matroids and greedy algorithms, approximation algorithms, multicommodity flows, and network design. This course is beneficial for all students of discrete mathematics, operations research, and computer science.
After completing this subject, students should:
Up to 50 pages of written assignments (30%: two assignments worth 15% each, due mid and late in semester), a 3-hour written examination (70%, in the examination period).
Lecture notes prepared by Dr Sanming Zhou, and the textbook by B. Korte and J. Vygen, Combinatorial Optimiation: Theory and Algorithms. 2nd Edition, Springer, Berlin, 2002
|Recommended Texts:|| |
|Breadth Options:|| |
This subject is not available as a breadth subject.
|Fees Information:||Subject EFTSL, Level, Discipline & Census Date|
In addition to learning specific skills that will assist students in their future careers in science, they will have the opportunity to develop generic skills that will assist them in any future career path. These include:
Doctor of Philosophy - Engineering |
Master of Operations Research and Management Science
Master of Philosophy - Engineering
Master of Science (Mathematics and Statistics)
Mathematics and Statistics |
Download PDF version.