Research Institute for Discrete Mathematics

Exercise class for the course "Combinatorial Optimization"

Winter term 2016/2017

Tuesdays, from 16:00 to 17:30 in the Seminarraum, Research Institute for Discrete Mathematics.

Exercise sets:

• Set 0 (unofficial, solved by the tutor in the first class)
• Set 1
• Set 2
• Set 3 and Programming Task 1
• Set 4
• Set 5
• Set 6
• Set 7
• Set 8
• Set 9
• Set 10

Programming Task 1:

The description of the task is at the end of Set 3 above. Here you will find some useful material (which will be updated once in a while).

• Precise definition of the DIMACS format
• Collection of DIMACS files of graph instances (134M) (last update: 2016 Nov 21)
• Collection of DIMACS files of matchings for each graph instance above (50M) (last update: 2016 Nov 21)
• List of maximum cardinalities of matchings for each graph instance above
• C++ unit with simple Graph class (last update: 2016 Nov 04)

• Removed a few graph instances (named "myciel...") from the collection above. These were weighted instances with some lines starting with 'n', which your program is not required to know how to handle.
• Fixed the number of edges in the instance "USA-road-d.USA.dmx". Somebody must have modified this file by hand (deleted lots of edges) and did not change the number of edges given in the first line.
• Added collection of matching instances! For each graph instance "<graph_name>.dmx" you will find a matching instance "<graph_name>_matching_maximal.dmx" which I created using a greedy algorithm that traverses the graph and extends the initial (empty) matching until it becomes maximal.
• Uploaded list of optimum values for our instances.