Bell Labs researchers have long been at the forefront of algorithmic sciences, computational sciences and other disciplines essential for managing complex systems.

Back in the 1950s, Joseph Kruskal and Robert Prim discovered two different efficient algorithms for computing a minimum spanning tree in a weighted graph. In the mid-1960s, researchers such as Ed Coffman, Ron Graham, David Johnson and Mike Garey were among the pioneers in the analysis of approximation algorithms and in multiprocessor scheduling. In the decades that followed, other Bell Labs researchers made landmark contributions in areas related to the mathematical foundations for bin-packing theory, stochastic planar matching theory, and NP-completeness theory.

More recently, Sasha Stolyar’s work on the Greedy Primal-Dual algorithm has yielded a method that maximizes the utility of a controlled queuing network while maintaining stability, if stability is feasible.

Asymptotic theory of schedulers for large-scale systems
Asymptotic theory of schedulers for large-scale systems

In the pursuit of more energy-efficient networks, researchers have used techniques from combinatorial optimization to provide guidance on minimizing the energy footprint of optical networks.

Vladimir Kolesnikov, in association with our research on privacy and security, is developing cryptographic algorithms that provide strong and novel ways for protecting personal data, including ways to prevent the administrator of a database from gaining any insights into the data as a result of the queries originating from a user.