Branch & Converge: A Generic Technique for Boundable Problems (Bachelor's Thesis defense)

To this end, we propose branch-and-converge, an abstract method applicable to problems over commutative, ordered monoids. Branch-and-bound can be regarded as a specialization of branch-and-converge using the minimum (or maximum) operator. Our method requires that a problem can be partitioned and that a partition's total value can be efficiently bounded from above and below. It iteratively yields tightening bounds and terminates eventually with the exact solution.

We then propose one possible approach to compute these partitions and their bounds for many problems over semirings, which is inspired by recent works in the area of combinatorial optimization. To this end, we present a formalism for describing finite sequences of valued state transitions which are combined to derive a solution. By merging or discarding states in specific ways as the exploration progresses, we can compute the information required by branch-and-converge. Our preliminary evaluation shows that branch-and-converge can be superior to a dynamic programming solution and that it can compete with existing solutions for the specific problem of counting independent sets on dense graphs. However, further work is required to determine the true practicability of our method.

--------------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.