Skip links

  • Skip to primary navigation
  • Skip to content
  • Skip to footer
Non Compos Mentis
  • About
  • Categories
  • Tags
  • Collections
  • Years
    • Algorithms: Design and Analysis II
      • About This Course
      • Problem Set 1
      • Homework 1 Optional Problems
      • Problem Set 2
      • Homework 2 Optional Problems
      • Problem Set 3
      • Homework 3 Optional Problems
      • Problem Set 4
      • Homework 4 Optional Problems
      • Problem Set 5
      • Homework 5 Optional Problems
      • Problem Set 6
      • Homework 6 Optional Problems
      • Final Exam

    Homework 6 Optional Problems

    Prove that in graphs with positive integer edge weights, the local search algorithm for the maximum cut problem is not guaranteed to converge in a polynomial number of iterations.

    ANSWER: See How Easy Is Local Search.

    Twitter Facebook LinkedIn
    Previous Next

    Comments

    You May Also Enjoy

    Brave Girls Don’t Cry

    About Kakenya Ntaiya, the CNN Hero who is empowering Maasai women in Kenya.

    Subversion to Git Migration

    Migrating from Subversion to Git.

    What’s Wrong with Java Collections - part I

    Shortcomings of the Java Collections Framework.

    Spring Cloud Netflix Eureka - The Hidden Manual

    Internal working of the Spring Cloud Eureka discovery service.

    • Feed
    © 2021 Abhijit Sarkar. Powered by Jekyll & Minimal Mistakes.