Continuous Relaxation for Discrete DC Programming

Takanori Maehara, Naoki Marumo, Kazuo Murota

Abstract

Discrete DC programming with convex extensible functions is studied. A natural approach for this problem is a continuous relaxation that extends the problem to a continuous domain and applies the algorithm in continuous DC programming. By employing a special form of continuous relaxation, which is named “lin-vex extension,” the optimal solution of the continuous relaxation coincides with the original discrete problem. The proposed method is demonstrated for the degree-concentrated spanning tree problem.
BibTeX
@article{maehara2018continuous,
  author = {Takanori Maehara and Naoki Marumo and Kazuo Murota},
  title = {{Continuous Relaxation for Discrete DC Programming}},
  journal = {Math. Program.},
  year = {2018},
  doi = {10.1007/s10107-017-1139-2},
}

Loading related content...

Figure