Attempting the Impossible: Enumerating Extremal Submodular Functions for n = 6
Our latest paper has appeared in the Recent Advances in Scientific Computing & Applications issue of Mathematics by MDPI! The paper furthers research into a type of mathematical function called submodular functions, which have been used in information inequalities, operational research, combinatorial optimization and social sciences, and they have also found fundamental applications in game theory and machine learning. Submodular functions can be thought of as occupying a region of space, and knowing where the vertices (actually, extremal rays) of this region are can simplify optimization problems to a simple search for the best vertex or ray. These rays had been listed for submodular functions defined over 3, 4 and 5 base elements. While for 5 elements there are only about 120,000 extremal rays, it was not known whether it would be possible to calculate all extremal rays for 6. This paper reports the results of attempting to do so. Using improved tools from po...
