Submodularity on a tree: Unifying $L^\natural$-convex and bisubmodular functions

Details Submodularity on a tree: Unifying $L^\natural$-convex and bisubmodular functions Submodularity on a tree: Unifying $L^\natural$-convex and bisubmodular functions

2010-07-07

arxiv.org/abs/1007.1229v3

Computer Science

Discrete Mathematics

14 pages

Scientific paper

We introduce a new class of functions that can be minimized in polynomial time in the value oracle model. These are functions $f$ satisfying $f(x)+f(y)\ge f(x \sqcap y)+f(x \sqcup y)$ where the domain of each variable $x_i$ corresponds to nodes of a rooted binary tree, and operations $\sqcap,\sqcup$ are defined with respect to this tree. Special cases include previously studied $L^\natural$-convex and bisubmodular functions, which can be obtained with particular choices of trees. We present a polynomial-time algorithm for minimizing functions in the new class. It combines Murota's steepest descent algorithm for $L^\natural$-convex functions with bisubmodular minimization algorithms.

Affiliated with

Also associated with

No associations

Rating

Submodularity on a tree: Unifying $L^\natural$-convex and bisubmodular functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Submodularity on a tree: Unifying $L^\natural$-convex and bisubmodular functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Submodularity on a tree: Unifying $L^\natural$-convex and bisubmodular functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-346454