Set Cover Problem

🔥 Vibe Prompt

"Solve set cover: 10 cities, 5 broadcast stations, each covering different cities. Find minimum stations."

def set_cover(universe, subsets):
    remaining = universe.copy()
    selected = []
    while remaining:
        best_name = None
        best_covered = 0
        for name, elements in subsets.items():
            if name not in selected:
                covered = len(remaining & elements)
                if covered > best_covered:
                    best_covered = covered
                    best_name = name
        if best_name:
            selected.append(best_name)
            remaining -= subsets[best_name]
        else:
            break
    return selected

universe = set(range(10))
subsets = {"A": {0,1,2,3}, "B": {3,4,5}, "C": {5,6,7}, "D": {7,8,9}, "E": {0,4,9}}
result = set_cover(universe, subsets)
print(f"Selected: {result}")

Chapter Summary

• Understand core concepts and principles
• Master implementation methods and techniques
• Familiar with common issues and solutions
• Able to apply in real projects

Further Reading

• Official documentation and API references
• Open source examples on GitHub
• Technical books and online courses
• Community discussions and tech blogs

Implementation Example

Basic Example

# This section provides a complete implementation example

Steps

1. Setup: Configure development environment
2. Data: Prepare required data
3. Implementation: Build core functionality
4. Testing: Verify correctness
5. Optimization: Improve performance

Common Errors

| Error Type | Cause | Solution | |------------|-------|----------| | Compilation | Syntax | Check code syntax | | Runtime | Environment | Verify dependencies installed | | Logic | Algorithm | Step-by-step debugging | | Performance | Efficiency | Use profilers |

Code Example

import sys

def main():
    print("Hello, World!")

if __name__ == "__main__":
    main()

References

• Official documentation
• API reference
• Open source examples
• Community discussions

Key Points

• Understand the core concepts thoroughly
• Practice with hands-on code examples
• Apply knowledge to real-world problems
• Review and reinforce through exercises

Further Learning

• Official documentation
• Open source projects on GitHub
• Community forums and discussions
• Related courses and tutorials

Greedy Set Cover Algorithm

Despite being NP-hard, a simple greedy algorithm provides a good approximation:

Algorithm

1. Initialize: uncovered = all elements, selected = []
2. While uncovered is not empty:
   • Pick the subset that covers the most uncovered elements
   • Add it to selected sets
   • Remove covered elements from uncovered
3. Return selected sets

Implementation

def greedy_set_cover(universe, subsets):
    """
    Greedy approximation algorithm for Set Cover.
    
    Args:
        universe: set of all elements that need to be covered
        subsets: dict {name: set_of_elements}
    
    Returns:
        list of subset names that cover all elements
    """
    uncovered = set(universe)
    selected = []
    
    while uncovered:
        # Find subset covering the most uncovered elements
        best_subset = None
        best_covered = 0
        
        for name, elements in subsets.items():
            covered = len(uncovered & elements)
            if covered > best_covered:
                best_covered = covered
                best_subset = name
        
        if best_covered == 0:
            break  # Cannot cover remaining elements
        
        selected.append(best_subset)
        uncovered -= subsets[best_subset]
    
    return selected


# Example
universe = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
subsets = {
    'A': {1, 2, 3, 4, 5},
    'B': {4, 5, 6, 7},
    'C': {6, 7, 8, 9, 10},
    'D': {1, 3, 5, 7, 9},
    'E': {2, 4, 6, 8, 10},
}

result = greedy_set_cover(universe, subsets)
print(f"Selected subsets: {result}")

Approximation Ratio

The greedy algorithm for Set Cover achieves an approximation ratio of ln(n) + 1, where n is the size of the largest subset. This means the greedy solution is at most ln(n) + 1 times worse than optimal.

| Universe Size | Max Approximation Ratio | |---------------|----------------------| | 10 | ~3.3x | | 100 | ~5.6x | | 1,000 | ~7.9x | | 10,000 | ~10.2x | | 100,000 | ~12.5x |

Applications

| Domain | Application | |--------|-------------| | Cloud Computing | Select minimum server configurations to cover all required features | | Network Security | Place minimum monitors to cover all network segments | | Sensor Networks | Position minimum sensors to cover an area | | Facility Location | Choose minimum warehouses to serve all cities | | Staff Scheduling | Assign minimum staff to cover all shifts | | Test Coverage | Select minimum tests to cover all code paths |

Summary

Set Cover is NP-hard, but the greedy algorithm provides a ln(n)-approximation in polynomial time. Pick the subset covering the most uncovered elements at each step. The greedy choice is locally optimal but globally approximate.

Key takeaways:

• Set Cover: cover all elements with minimum subsets
• NP-hard — no polynomial-time optimal solution exists
• Greedy: always pick subset covering most uncovered elements
• Approximation ratio: ln(n) + 1
• Fast: O(m × n) where m = subsets, n = universe size
• Applications: server selection, sensor placement, test coverage
• The greedy solution is near-optimal for practical cases

What's Next: Scheduling API

The next chapter builds a scheduling API — applying greedy scheduling algorithms in a real API service.