Instructor “RG” made a little editing for the sake of presentation:
A.: For my report for the Algorithm Design course I would like to write about min- or max-cut randomization of graphs or maybe a comparison of both of them. Would this be alright?
RG: Ok A., please send me a sketch of the organization when you are ready.
A.: Attached you can find the basic outline for my report:
Min-Cut vs. Max-Cut randomization for Graphs 0. Introduction 1. Basics 2. Min-Cut 3. Max-Cut 4. Comparison 5. Conclusion 6. References
RG: are you discussing also somehow the approx limitations of the max cut problem?
A.: I could add a subchapter about the approximation limitations in the Max-Cut chapter or write something about it in the Basic Idea of Max-Cut subchapter.
RG: Ok A., please proceed to the next step.
A.: Attached you can find an updated and more detailed outline for my report.
Min-Cut vs. Max-Cut randomization for Graphs
0. Introduction Introduction to the reports topic and goals: - Explain the idea of Min-Cut and Max-Cut - Comparison of the approaches 1. Basics Give some basic definitions for later used concepts in the report a. Graphs Description of the basic understanding of Graphs and Multigraphs in the context of this report b. Randomizations Definition of Randomization in the context of this report 2. Min-Cut a. Basic Idea of Min-Cut - Description about how min-cut works - Example graph for Min-Cut b. Better Min-Cut Description of how the probability of the algorithm can be improved 3. Max-Cut a. Basic Idea of Max-Cut - Description of the basic idea behing Max-Cut - Example graph for Max-Cut b. Approximation Limitations Description of the limitations for the approximation of Max-Cut c. Approaches for Max-Cut Description of the different approaches of Max-Cut we have learned i. Local Search Description of the algorithm we learned in the lecture with example graph ii. Greedy Description of Greedy algorithm from the lecture iii. Randomization and Derandomization - Max-Cut with randomization and with derandomization - Use of universal hash functions and conditional expectations 4. Comparison Runtime and output comparison a. Similarities of the Cut randomization Where are the approaches similar b. Differences Where are the obvious and not so obvious differences between the approaches of Min- and Max-Cut c. Uses Description where the different approaches are being used and how effectful they are being used 5. Conclusion Summary of the different approaches mentioned in the report and of the results of the comparison 6. References List of references that were used in this report
RG: Very good plan! You can proceed and finalize the report. When ready, contact me, so we can fix a date to read togther and comment your report in my office.