Maiko Shigeno
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Maiko Shigeno has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Kazuo Murota
Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan , JP
1 shared publication S. Thomas McCormick
Faculty of Commerce and Business Administration, University of British Columbia, Vancouver, British Columbia V6T 1Z2 Canada
1 shared publicationSatoru Iwata
Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606, Japan
1 shared publication- Satoru Iwata
University of Tokyo
1 shared publication - Satoru Iwata
The University of Tokyo
1 shared publication
Latest Publications
- 1 February 2000
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 25 (1) , 76-104
Relaxed Most Negative Cycle and Most Positive Cut Canceling Algorithms for Minimum Cost Flow
This paper presents two new scaling algorithms for the minimum cost network flow problem, one a primal cycle canceling algorithm, the other a dual cut canceling algorithm. Both algorithms scale a relaxed optimality parameter, and create a second, inner relaxation. The primal algorithm uses the inner relaxation to cancel a most negative node-disjoint family of cycles w.r.t. the scaled parameter, the dual algorithm uses it to cancel most positive cuts w.r.t. the scaled parameter. We show that in a network with n nodes and m arcs, both algorithms need to cancel only O(mn) objects per scaling phase. Furthermore, we show how to efficiently implement both algorithms to yield weakly polynomial running times that are as fast as any other cycle or cut canceling algorithms. Our algorithms have potential practical advantages compared to some other canceling algorithms as well. Along the way, we give a comprehensive survey of cycle and cut canceling algorithms for min-cost flow. We also clarify the formal duality between cycles and cuts.
- 1 February 2000
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 25 (1) , 76-104
Relaxed Most Negative Cycle and Most Positive Cut Canceling Algorithms for Minimum Cost Flow
This paper presents two new scaling algorithms for the minimum cost network flow problem, one a primal cycle canceling algorithm, the other a dual cut canceling algorithm. Both algorithms scale a relaxed optimality parameter, and create a second, inner relaxation. The primal algorithm uses the inner relaxation to cancel a most negative node-disjoint family of cycles w.r.t. the scaled parameter, the dual algorithm uses it to cancel most positive cuts w.r.t. the scaled parameter. We show that in a network with n nodes and m arcs, both algorithms need to cancel only O(mn) objects per scaling phase. Furthermore, we show how to efficiently implement both algorithms to yield weakly polynomial running times that are as fast as any other cycle or cut canceling algorithms. Our algorithms have potential practical advantages compared to some other canceling algorithms as well. Along the way, we give a comprehensive survey of cycle and cut canceling algorithms for min-cost flow. We also clarify the formal duality between cycles and cuts.
- 1 November 1997
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 22 (4) , 803-813
A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
This paper presents a fast algorithm to solve the intersection problem for a pair of nondecreasing and nonincreasing strong map sequences of submodular systems. The worst-case time bound is the same as that of the push/relabel algorithm for a single intersection problem. This extends the Gallo-Grigoriadis-Tarjan (GGT) method for parametric maximum flow problems and reveals an algorithmic significance of the concept of strong maps for submodular systems.
- 1 November 1997
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 22 (4) , 803-813
A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
This paper presents a fast algorithm to solve the intersection problem for a pair of nondecreasing and nonincreasing strong map sequences of submodular systems. The worst-case time bound is the same as that of the push/relabel algorithm for a single intersection problem. This extends the Gallo-Grigoriadis-Tarjan (GGT) method for parametric maximum flow problems and reveals an algorithmic significance of the concept of strong maps for submodular systems.
- 1 March 1997
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 73 (3) , 261-273
A cost-scaling algorithm for 0–1 submodular flows
- 1 March 1997
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 73 (3) , 261-273
A cost-scaling algorithm for 0–1 submodular flows