Network Optimisation
Subject MAST90013 (2011)
Note: This is an archived Handbook entry from 2011.
| Credit Points: | 12.50 | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Level: | 9 (Graduate/Postgraduate) | ||||||||||||
| Dates & Locations: | This subject has the following teaching availabilities in 2011: Semester 2, Parkville - Taught on campus.
On-campus. Timetable can be viewed here. For information about these dates, click here. | ||||||||||||
| Time Commitment: | Contact Hours: 36 hours comprising 1 two-hour lectures per week and 1 one-hour practice class per week. Total Time Commitment: 3 contacts and 7 hours private study per week. | ||||||||||||
| Prerequisites: | None. | ||||||||||||
| Corequisites: | None. | ||||||||||||
| Recommended Background Knowledge: | An introductory level subject in operations research (equivalent to 620-290 Discrete Mathematics and Operations Research) and a third year subject in graph theory (equivalent to 620-352 Graph Theory). | ||||||||||||
| Non Allowed Subjects: | None. | ||||||||||||
| Core Participation Requirements: |
For the purposes of considering requests for Reasonable Adjustments under the Disability Standards for Education (Cwth 2005), and Students Experiencing Academic Disadvantage Policy, academic requirements for this subject are articulated in the Subject Description, Subject Objectives, Generic Skills and Assessment Requirements for this entry. The University is dedicated to provide support to those with special requirements. Further details on the disability support scheme can be found at the Disability Liaison Unit website: http://www.services.unimelb.edu.au/disability/ |
| Subject Overview: | 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. |
|---|---|
| Objectives: | After completing this subject, students should: - be able to understand aspects of network optimisation problems and the methodologies to solve them; - develop the abilities needed to design combinatorial algorithms for solving other network problems not covered in the subject; - have the ability to pursue further studies in this and related areas. |
| Assessment: | Up to 50 pages of written assignments (40%: two assignments worth 20% each, due mid and late in semester), a 3 hour written examination (60%, in the examination period). |
| Prescribed Texts: | 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: | TBA |
| Breadth Options: | This subject is not available as a breadth subject. |
| Fees Information: | Subject EFTSL, Level, Discipline & Census Date |
| Generic Skills: | 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: * problem-solving skills: the ability to engage with unfamiliar problems and identify relevant solution strategies; * analytical skills: the ability to construct and express logical arguments and to work in abstract or general terms to increase the clarity and efficiency of analysis; * collaborative skills: the ability to work in a team; * time-management skills: the ability to meet regular deadlines while balancing competing commitments. |
| Related Course(s): |
Master of Operations Research and Management Science Master of Science (Mathematics and Statistics) |
Download PDF version.