• Skip to primary navigation
  • Skip to content
  • Skip to footer
Non Compos Mentis
  • About
  • Categories
  • Tags
  • Collections
    • 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.

    Tags: algorithm-design, algorithms, computer-science, data-structures, programming, technical

    Updated: May 14, 2025

    Share on

    X Facebook LinkedIn Bluesky
    Previous Next

    Leave a comment

    You may also enjoy

    Signing Artifacts for Publishing to Maven Central Repository

    Signing Artifacts for Publishing to Maven Central Repository.

    grPC Health Checks on Kubernetes with Spring Boot Actuator

    grPC Health Checks on Kubernetes with Spring Boot Actuator.

    Task Scheduling

    Scheduling interdependent tasks.

    Couchbase on Kubernetes

    Running Couchbase Server on Kubernetes.

    • Follow:
    • Feed
    © 2025 Abhijit Sarkar. Powered by Jekyll & Minimal Mistakes.