Scaling Algorithms for M-Convex Function Minimization
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.922-929
- Publication Date
- 2002/05/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Satoko MORIGUCHI, Kazuo MUROTA, Akiyoshi SHIOURA, "Scaling Algorithms for M-Convex Function Minimization" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 922-929, May 2002, doi: .
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_922/_p
Copy
@ARTICLE{e85-a_5_922,
author={Satoko MORIGUCHI, Kazuo MUROTA, Akiyoshi SHIOURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Scaling Algorithms for M-Convex Function Minimization},
year={2002},
volume={E85-A},
number={5},
pages={922-929},
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={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Scaling Algorithms for M-Convex Function Minimization
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 922
EP - 929
AU - Satoko MORIGUCHI
AU - Kazuo MUROTA
AU - Akiyoshi SHIOURA
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2002
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.
ER -
English
