DidaWiki

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.