Algorithms for Discrete Structure
Among many targets that computers treat, objects that have discrete structures, such as sets and strings are an interesting target.Our research aims at developing efficient and practical algorithms for discrete structures.
In particular, we mainly focus on a research type that utilizes a special data structure called zero-suppresed binary decision diagram. The data structure allows us to hold a set of "all combinations that satisfy a given condition" compactly.
Enumerating combinations
Assume that we want to deal with combinations that satisfy some given conditions. If we can store them in a database compactly, we can use them for many problems that involve combinations, such as data retrieval and combinatorial optimizations.
Among such combinations, we focused on a type of combination called "exact cover".
An exact cover is a laying out of given pieces without any gaps. In the real world, this problem corresponds to layouts of modules in an electronic circuit board or layouts of an apartment room.
For finding all solutions of a given exact cover problem, we achieved over 10,000 times faster than conventional methods. For example, for laying out tetrominoes in 12 x 12 cells, we found that there are exactly 13,664,822,582,333,502,156,627,512 possible ways of laying out.
Equilibrium computation of games
When many people share the same set of resources, such as roads and communication networks, changes in resource congestion can be viewed as a "congestion game," a type of game theory.
When viewed as a congestion game, if each user selfishly selects a small-cost route without direction or control, the degree of congestion for each resource component can be determined as the equilibrium of the congestion game.
Conventionally, the equilibrium could not be obtained even for a small network, because it required huge computational time. By using a binary decision diagram to represent a set of paths compactly, we realized vastly faster equilibrium computations even for practical size networks.
Applications to network design
In networks such as communication networks or power grid networks, when operators consider reinforcing, reliability is one of the most important indicators to respect.
When we treat network reliability, we have to consider not only the reliability of individual elements but also the reliability of the entire network. However, it was difficult to calculate it because it contains calculations for a huge number of combinations of a network component. To tackle this problem, we devised an A*-style search method that works on a decision diagram. The algorithm allows us to find exactly the most reliable way to reinforce the network within a given budget.
