A groundbreaking study has improved the binary matching problem in computer science by simulating the connections between neurons and fibers in the nervous system. This method not only improves the matching performance in applications like ride-sharing services, but also enhances privacy by being done in a distributed manner, without the need for a central server.
Introduce
The binary matching problem is one of the most important challenges in computer science, widely applied in areas ranging from ride-sharing services, organ transplants, to medical training programs. This problem requires optimizing the pairing between two different populations (e.g., drivers and passengers) to minimize costs and enhance user experience.
Recently, researcher Saket Navlakha at Cold Spring Harbor Laboratory has come up with a new method, inspired by the nervous systems of living organisms. This new algorithm not only optimizes the efficiency of matching, but also solves one of the major limitations of current methods: the dependence on a central server to process the data.
Method
1. Binary matching problem and current constraints
In current systems such as car sharing services, when a passenger requests a ride, servers collect information from various sources to match the passenger with a driver. However, this requires all the information to be sent to a central server for processing. This is not only time-consuming but also reduces user privacy.
2. Inspired by the nervous system
In the nervous system of living organisms, neurons initially connect to many muscle fibers, but through competition, each neuron eventually pairs with only one muscle fiber. Navlakha discovered that this process is a kind of binary matching problem, and he applied this principle to computer science.
Instead of having all the information concentrated on one central server, neurons in the nervous system conduct their own “bids” based on neurotransmitter transmission. The neuron that sends the strongest signal wins the right to connect to the muscle fiber, while the neurons that fail will switch to connect to another muscle fiber. This bidding process does not require a central coordination center and still ensures optimal efficiency.
This diagram illustrates how the body’s motor neurons connect to muscle fibers before (left) and after (right) developmental pruning. As Navlakha explains, “Each clump corresponds to a motor unit. Small motor units are highly active, recruited first during contraction (because their neurons have a low firing threshold), and produce small forces. Meanwhile, large motor units are less active, recruited last (because their neurons have a high firing threshold), and produce larger forces.”
Research from Navlakha Laboratory, Cold Spring Harbor Laboratory
3. Distributed algorithms
The new algorithm is based on two simple equations:
- Competition between partners: Drivers and passengers compete to find the most optimal partner, similar to neurons bidding on muscle fibers.
- Resource reallocation: If an object (driver or passenger) fails, they reallocate resources and find another object within their range, instead of sending all information to one server.
4. Real-world examples of distributed systems
Consider the situation in a ride-sharing service. Each driver and passenger does not need to send their location to a dispatch center. Instead, each driver will only know the nearest passengers (which can be received over a communication range of about 5 km), and will send suggestions based on distance or estimated time to reach the pickup point. Passengers will receive these suggestions and choose the driver with the shortest travel time.
If a driver is not selected, they continue to “bid” with other passengers near them, and vice versa, passengers can also adjust their choices based on new offers. This way, there is no need for a central server to compare all the data of all drivers and passengers. The pairing decision is made through local computations, much like how the nervous system works.
An easier to understand example:
- Imagine a marketplace where each seller searches for buyers near them. Sellers invite buyers who are closest to them, and buyers compare the closest sellers for the best prices. If a seller is not selected, they move on to invite others. There is no one person who coordinates the entire marketplace, but through this self-communicating process, each seller and buyer eventually come together based on local optimization criteria.
In this system, each pairing decision is made by the subjects themselves without centralizing all information at a single decision center.
Result
When compared to the best current matching algorithms, the new algorithm shows superior performance. It generates near-globally optimal matches without the need for a central coordinator, which reduces waiting times in real-world applications such as car-sharing services. In addition, this method also ensures better privacy because it does not need to collect all data on a single server.
Conclude
The neural-inspired distributed method not only improves the binary matching problem, but also opens up a wide range of real-world applications, from car-sharing systems to online auctions. Importantly, it preserves privacy and avoids the need for central servers. Navlakha hopes that this research will inspire other scientists to develop distributed algorithm-based tools for more complex applications in the future.
Reference
Navlakha, S. et al., 2024, A neural algorithm for computing bipartite matchings, Proceedings of the National Academy of Sciences, DOI: 10.1073/pnas.2321032121.