Scaling algorithms for M-convex function minimization

Satoko Moriguchi; Kazuo Murota; Akiyoshi Shioura

Scaling algorithms for M-convex function minimization

Satoko Moriguchi, Kazuo Murota, Akiyoshi Shioura

INF - System Information Sciences

Research output: Contribution to journal › Article › peer-review

16 Citations (Scopus)

Abstract

M-convex functions have various desirable properties as convexity in discrete optimization. We can find a global minimum of an M-convex function by a greedy algorithm, i.e., so-called descent algorithms work for the minimization. In this paper, we apply a scaling technique to a greedy algorithm and propose an efficient algorithm for the minimization of an M-convex function. Computational results are also reported.

Original language	English
Pages (from-to)	922-929
Number of pages	8
Journal	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Volume	E85-A
Issue number	5
Publication status	Published - 2002 May

Keywords

Convex function
Discrete optimization
Matroid
Scaling algorithm

ASJC Scopus subject areas

Signal Processing
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering
Applied Mathematics

Cite this

@article{b412d53be8d1414aa8953ea27b891b49,

title = "Scaling algorithms for M-convex function minimization",

abstract = "M-convex functions have various desirable properties as convexity in discrete optimization. We can find a global minimum of an M-convex function by a greedy algorithm, i.e., so-called descent algorithms work for the minimization. In this paper, we apply a scaling technique to a greedy algorithm and propose an efficient algorithm for the minimization of an M-convex function. Computational results are also reported.",

keywords = "Convex function, Discrete optimization, Matroid, Scaling algorithm",

author = "Satoko Moriguchi and Kazuo Murota and Akiyoshi Shioura",

year = "2002",

month = may,

language = "English",

volume = "E85-A",

pages = "922--929",

journal = "IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences",

issn = "0916-8508",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "5",

}

TY - JOUR

T1 - Scaling algorithms for M-convex function minimization

AU - Moriguchi, Satoko

AU - Murota, Kazuo

AU - Shioura, Akiyoshi

PY - 2002/5

Y1 - 2002/5

N2 - M-convex functions have various desirable properties as convexity in discrete optimization. We can find a global minimum of an M-convex function by a greedy algorithm, i.e., so-called descent algorithms work for the minimization. In this paper, we apply a scaling technique to a greedy algorithm and propose an efficient algorithm for the minimization of an M-convex function. Computational results are also reported.

AB - M-convex functions have various desirable properties as convexity in discrete optimization. We can find a global minimum of an M-convex function by a greedy algorithm, i.e., so-called descent algorithms work for the minimization. In this paper, we apply a scaling technique to a greedy algorithm and propose an efficient algorithm for the minimization of an M-convex function. Computational results are also reported.

KW - Convex function

KW - Discrete optimization

KW - Matroid

KW - Scaling algorithm

UR - http://www.scopus.com/inward/record.url?scp=0036579177&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036579177&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0036579177

SN - 0916-8508

VL - E85-A

SP - 922

EP - 929

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 5

ER -

Scaling algorithms for M-convex function minimization

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this