{'fraction_non_alphanumeric': 0.040106951871657755, 'fraction_numerical': 0.004010695187165776, 'mean_word_length': 4.427536231884058, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Chapter 6 Approximation algorithms

Figure 6.1: Example. For this problem, the greedy algorithm will always take the vertex with the highest degree (i.e., the one covering the largest number of edges), add it to the cover set, remove it from the graph, and repeat. We will refer to this algorithm as GreedyVertexCover. It is not too hard to see that this algorithm does not output the optimal vertex-cover. Indeed, consider the graph depicted on the right. Clearly, the optimal solution is the black vertices, but the greedy algorithm would pick the four white vertices. This of course still leaves open the possibility that, while we do not get the optimal vertex cover, what we get is a vertex cover which is “relatively good” (or “good enough”).