Prismatic Algorithm for Discrete D.C. Programming Problems

Details Prismatic Algorithm for Discrete D.C. Programming Problems Prismatic Algorithm for Discrete D.C. Programming Problems

2011-08-21

arxiv.org/abs/1108.4217v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper, we propose the first exact algorithm for minimizing the difference of two submodular functions (D.S.), i.e., the discrete version of the D.C. programming problem. The developed algorithm is a branch-and-bound-based algorithm which responds to the structure of this problem through the relationship between submodularity and convexity. The D.S. programming problem covers a broad range of applications in machine learning because this generalizes the optimization of a wide class of set functions. We empirically investigate the performance of our algorithm, and illustrate the difference between exact and approximate solutions respectively obtained by the proposed and existing algorithms in feature selection and discriminative structure learning.

Affiliated with

Also associated with

No associations

Rating

Prismatic Algorithm for Discrete D.C. Programming Problems 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 Prismatic Algorithm for Discrete D.C. Programming Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prismatic Algorithm for Discrete D.C. Programming Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-174975