A coordinatewise domain scaling algorithm for M-convex function minimization

Research output: Contribution to journalConference articlepeer-review

5 Citations (Scopus)


We present a polynomial time domain scaling algorithm for the minimization of an M-convex function. M-convex functions are nonlinear discrete functions with (poly)matroid structures, which are being recognized to play a fundamental role in tractable cases of discrete optimization. The novel idea of the algorithm is to use an individual scaling factor for each coordinate.

Original languageEnglish
Pages (from-to)21-35
Number of pages15
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2337 LNCS
Publication statusPublished - 2002 Dec 1
Externally publishedYes
Event9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002 - Cambridge, MA, United States
Duration: 2002 May 272002 May 29

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A coordinatewise domain scaling algorithm for M-convex function minimization'. Together they form a unique fingerprint.

Cite this