Drill Bits

Sort By:

Efficient Graph Search

Welcome to Drill Bits, a new column about programming. This inaugural episode shows how graph search algorithms can avoid unnecessary work. A simple modification to classic breadth-first search improves the lower bound on its running time: Whereas classic BFS always requires time proportional to the number of vertices plus the number of edges, the improved "Efficient BFS" sometimes runs in time proportional to the number of vertices alone. Both asymptotic analysis and experiments show that Efficient BFS can be much faster than classic BFS.

September 13, 2020

Topic: Visualization


Decentralized Computing

Feeding all relevant inputs to a central solver is the obvious way to tackle a problem, but it's not always the only way. Decentralized methods that make do with only local communication and local computation are sometimes the best way. This episode of Drill Bits reviews an elegant protocol for self-organizing wireless networks that can also solve a seemingly impossible social networking problem. The protocol preserves privacy among participants and is so simple that it can be implemented with pencil, paper, and postcards. Example software implements both the decentralized protocol and a centralized solver.

November 16, 2020

Topic: Distributed Computing


Offline Algorithms in Low-Frequency Trading:
Clearing Combinatorial Auctions

Expectations run high for software that makes real-world decisions, particularly when money hangs in the balance. This third episode of the Drill Bits column shows how well-designed software can effectively create wealth by optimizing gains from trade in combinatorial auctions. We'll unveil a deep connection between auctions and a classic textbook problem, we'll see that clearing an auction resembles a high-stakes mutant Tetris, we'll learn to stop worrying and love an NP-hard problem that's far from intractable in practice, and we'll contrast the deliberative business of combinatorial auctions with the near-real-time hustle of high-frequency trading.

January 27, 2021

Topic: Development