Archive for the 'Computational Complexity' Category

Winning an election with 22% of the popular vote

Monday, November 1st, 2004

A presidential candidate could be elected with as a little as 21.8% of the popular vote by getting just over 50% of the votes in DC and each of 39 small states. This is true even when everyone votes and there are only two candidates. In other words, a candidate could lose with 78.2% of the popular vote by getting just under 50% in small states and 100% in large states.

The optimal set of states to take (the one that lets a candidate win with the smallest popular vote) is not the N states with the smallest population. It's also not the N states with the smallest value for (population/electors), which would be optimal if you could get exactly 270 electoral votes that way.

The optimal solution happens to get exactly 270 electoral votes. In this solution, the winner takes DC, the 37 smallest states, the 39th smallest state, and the 40th smallest state. (The winner takes Alabama, Alaska, Arizona, Arkansas, Colorado, Connecticut, Delaware, DC, Hawaii, Idaho, Indiana, Iowa, Kansas, Kentucky, Louisiana, Maine, Maryland, Minnesota, Mississippi, Missouri, Montana, Nebraska, Nevada, New Hampshire, New Mexico, North Carolina, North Dakota, Oklahoma, Oregon, Rhode Island, South Carolina, South Dakota, Tennessee, Utah, Vermont, Virginia, Washington, West Virginia, Wisconsin, and Wyoming.)

Read on for my assumptions and algorithm.

Read the rest of this entry »

Garey and Johnson

Saturday, July 31st, 2004

My copy of Garey and Johnson arrived the other day. I wonder if it will make good airplane reading while I'm heading to Mozilla Developer Day next week.


Monday, September 1st, 2003

I bought a textbook, some paper, and some binders at Huntley Bookstore today. I asked the guy at checkout to put my purchase in two bags of roughly equal weight. He thought this was a strange request and expressed uncertainty about his solution, but the bags felt balanced as I walked back to my dorm.

Only later did I realize my grave mistake: I had casually asked him to solve an NP-complete problem.