Esej ilustruje dwa problemy optymalizacyjne. Pierwszy to dominowanie w grafach (kratowych): klasyczne i rzymskie. Drugi problem to pokrycie wierzchołkowe w grafach 2-dzielnych. W szczególności pokazujemy, że algorytmy zachłanne nie gwarantują uzyskania rozwiązania optymalnego, nawet wówczas gdy problem da się rozwiązać w czasie wielomianowym.
Authors
Additional information
- Category
- Publikacja w czasopiśmie
- Type
- artykuły w czasopismach
- Language
- polski
- Publication year
- 2024
