Reproduce “Optimization of Sums of Bivariate Functions: An Introduction to Relaxation-Based Methods for the Case of Finite Domains” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Nils Müller
Nils Müller provides a unified derivation of relaxation-based optimization methods for sums of bivariate functions on finite domains, demonstrating the NP-equivalence of the general problem while identifying tree-structured instances as exactly solvable with dynamic programming. The research develops novel algorithms and empirically validates their performance across diverse problem classes like signal reconstruction, where they achieve low primal objective values and small relaxation gaps.
Key insights
- Optimizing sums of bivariate functions is NP-equivalent in the general case, but becomes exactly solvable in polynomial time using Dynamic Programming when the underlying graph structure is a tree.
- Strong duality holds for star and entropy-regularized star relaxations, with unique, closed-form optimal solutions available for the entropy-regularized dual.
- While exact for tree-structured graphs, the global measure generally cannot be uniquely reconstructed from bivariate marginals for non-tree graphs, highlighting the inherent approximation nature of many relaxation methods.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.