Akiyoshi Shioura
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
Akiyoshi Shioura has a total of 38 co-authors. Here are the top co-authors by number of shared publications:
- Vitaly A. Strusevich
School of Computing and Mathematical Sciences, University of Greenwich, London, UK
8 shared publications - Kazuo Murota
The Institute of Statistical Mathematics, Tachikawa, Japan
7 shared publications Natalia V. Shakhlevich
University of Leeds
4 shared publications- Natalia V. Shakhlevich
School of Computing, University of Leeds, Leeds, UK
4 shared publications Kazuo Murota
Tokyo Metropolitan University
3 shared publicationsTakeshi Tokuyama
3 shared publications
Latest Publications
- 26 August 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (3) , 1369-1394
Steepest Descent Algorithm for M-Convex Function Minimization Using Long Step Length
We consider the minimization of an M-convex function, which is a discrete convexity concept for functions on the integer lattice points. It is known that a minimizer of an M-convex function can be obtained by the steepest descent algorithm. In this paper, we propose an effective use of long step length in the steepest descent algorithm, aiming at a reduction in the running time. In particular, we obtain an improved time bound by using long step length. We also consider the constrained M-convex function minimization and show that long step length can be applied to a variant of the steepest descent algorithm as well.
- 26 August 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (3) , 1369-1394
Steepest Descent Algorithm for M-Convex Function Minimization Using Long Step Length
We consider the minimization of an M-convex function, which is a discrete convexity concept for functions on the integer lattice points. It is known that a minimizer of an M-convex function can be obtained by the steepest descent algorithm. In this paper, we propose an effective use of long step length in the steepest descent algorithm, aiming at a reduction in the running time. In particular, we obtain an improved time bound by using long step length. We also consider the constrained M-convex function minimization and show that long step length can be applied to a variant of the steepest descent algorithm as well.
- Open Access
Steepest Descent Algorithm for M-convex Function Minimization Using Long Step Length
We consider the minimization of an M-convex function, which is a discrete convexity concept for functions on the integer lattice points. It is known that a minimizer of an Mconvex function can be obtained by the steepest descent algorithm. In this paper, we propose an effective use of long step length in the steepest descent algorithm, aiming at the reduction in the running time. In particular, we obtain an improved time bound by using long step length. We also consider the constrained M-convex function minimization and show that long step length can be applied to a variant of steepest descent algorithm as well.
Open AccessSteepest Descent Algorithm for M-convex Function Minimization Using Long Step Length
We consider the minimization of an M-convex function, which is a discrete convexity concept for functions on the integer lattice points. It is known that a minimizer of an Mconvex function can be obtained by the steepest descent algorithm. In this paper, we propose an effective use of long step length in the steepest descent algorithm, aiming at the reduction in the running time. In particular, we obtain an improved time bound by using long step length. We also consider the constrained M-convex function minimization and show that long step length can be applied to a variant of steepest descent algorithm as well.
- Open Access
An Improved Proximity Bound for Bike-Dock Reallocation Problem in Bike Sharing System
We consider a class of nonlinear integer programming problems arising from re-allocation of dock-capacity in a bike sharing system. The main aim of this note is to derive an improved proximity bound for the problem and its scaled variant. This makes it possible to refine the time bound for the polynomial-time proximity-scaling algorithm by Freund et al. (2022).
Open AccessAn Improved Proximity Bound for Bike-Dock Reallocation Problem in Bike Sharing System
We consider a class of nonlinear integer programming problems arising from re-allocation of dock-capacity in a bike sharing system. The main aim of this note is to derive an improved proximity bound for the problem and its scaled variant. This makes it possible to refine the time bound for the polynomial-time proximity-scaling algorithm by Freund et al. (2022).
- Open Access
- 31 October 2024
- Published by The Operations Research Society of Japan in Journal of the Operations Research Society of Japan
- Vol. 67 (4) , 111-125
NOTE ON POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR INTEGRATED NETWORK DESIGN AND SCHEDULING PROBLEMS
In the integrated network design and scheduling (INDS) problem, we are asked to repair edges in a graph by using parallel machines so that the performance of the network is recovered by a certain level, and the objective is to minimize the makespan required to finish repairing edges. The main aim of this note is to show that polynomial-time approximation schemes exist for various families of the INDS problems with a constant number of parallel machines, including the problems associated with minimum spanning tree, shortest path, maximum edge-disjoint paths, and maximum-weight matching.
- 31 October 2024
- Published by The Operations Research Society of Japan in Journal of the Operations Research Society of Japan
- Vol. 67 (4) , 111-125
Open AccessNOTE ON POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR INTEGRATED NETWORK DESIGN AND SCHEDULING PROBLEMS
In the integrated network design and scheduling (INDS) problem, we are asked to repair edges in a graph by using parallel machines so that the performance of the network is recovered by a certain level, and the objective is to minimize the makespan required to finish repairing edges. The main aim of this note is to show that polynomial-time approximation schemes exist for various families of the INDS problems with a constant number of parallel machines, including the problems associated with minimum spanning tree, shortest path, maximum edge-disjoint paths, and maximum-weight matching.
- Open Access
- 8 December 2023
- Published by Springer Nature in Japan Journal of Industrial and Applied Mathematics
- Vol. 41 (2) , 857-880
Note on minimization of quasi M$^{\natural }$-convex functionsFor a class of discrete quasi convex functions called semi-strictly quasi M $$^{\natural }$$ -convex functions, we investigate fundamental issues relating to minimization, such as optimality condition by local optimality, minimizer cut property, geodesic property, and proximity property. Emphasis is put on comparisons with (usual) M $$^{\natural }$$ -convex functions. The same optimality condition and a weaker form of the minimizer cut property hold for semi-strictly quasi M $$^{\natural }$$ -convex functions, while geodesic property and proximity property fail.- 8 December 2023
- Published by Springer Nature in Japan Journal of Industrial and Applied Mathematics
- Vol. 41 (2) , 857-880
Open AccessNote on minimization of quasi M$^{\natural }$-convex functionsFor a class of discrete quasi convex functions called semi-strictly quasi M $$^{\natural }$$ -convex functions, we investigate fundamental issues relating to minimization, such as optimality condition by local optimality, minimizer cut property, geodesic property, and proximity property. Emphasis is put on comparisons with (usual) M $$^{\natural }$$ -convex functions. The same optimality condition and a weaker form of the minimizer cut property hold for semi-strictly quasi M $$^{\natural }$$ -convex functions, while geodesic property and proximity property fail. - Open Access
Note on Minimization of Quasi M$^\natural$-convex Functions
For a class of discrete quasi convex functions called semi-strictly quasi M$^\natural$-convex functions, we investigate fundamental issues relating to minimization, such as optimality condition by local optimality, minimizer cut property, geodesic property, and proximity property. Emphasis is put on comparisons with (usual) M$^\natural$-convex functions. The same optimality condition and a weaker form of the minimizer cut property hold for semi-strictly quasi M$^\natural$-convex functions, while geodesic property and proximity property fail.
Open AccessNote on Minimization of Quasi M$^\natural$-convex Functions
For a class of discrete quasi convex functions called semi-strictly quasi M$^\natural$-convex functions, we investigate fundamental issues relating to minimization, such as optimality condition by local optimality, minimizer cut property, geodesic property, and proximity property. Emphasis is put on comparisons with (usual) M$^\natural$-convex functions. The same optimality condition and a weaker form of the minimizer cut property hold for semi-strictly quasi M$^\natural$-convex functions, while geodesic property and proximity property fail.
- Open Access
Note on Steepest Descent Algorithm for Quasi L$^{\natural}$-convex Function Minimization
We define a class of discrete quasi convex functions, called semi-strictly quasi L$^{\natural}$-convex functions, and show that the steepest descent algorithm for L$^{\natural}$-convex function minimization also works for this class of quasi convex functions. The analysis of the exact number of iterations is also extended, revealing the so-called geodesic property of the steepest descent algorithm when applied to semi-strictly quasi L$^{\natural}$-convex functions.
Open AccessNote on Steepest Descent Algorithm for Quasi L$^{\natural}$-convex Function Minimization
We define a class of discrete quasi convex functions, called semi-strictly quasi L$^{\natural}$-convex functions, and show that the steepest descent algorithm for L$^{\natural}$-convex function minimization also works for this class of quasi convex functions. The analysis of the exact number of iterations is also extended, revealing the so-called geodesic property of the steepest descent algorithm when applied to semi-strictly quasi L$^{\natural}$-convex functions.
- Open Access
- 4 July 2023
- Published by Springer Nature in Japan Journal of Industrial and Applied Mathematics
- Vol. 41 (1) , 359-380
Characterization and algorithm for bivariate multi-unit assignment valuations
A multi-unit assignment valuation is a function represented by a weighted bipartite graph. In this paper, we provide a characterization of such a function in terms of maximizer sets of perturbed functions. We then present an algorithm that checks whether a given bivariate function is a multi-unit assignment valuation, and if the answer is “yes,” computes a weighted bipartite graph representing the function.
- 4 July 2023
- Published by Springer Nature in Japan Journal of Industrial and Applied Mathematics
- Vol. 41 (1) , 359-380
Open AccessCharacterization and algorithm for bivariate multi-unit assignment valuations
A multi-unit assignment valuation is a function represented by a weighted bipartite graph. In this paper, we provide a characterization of such a function in terms of maximizer sets of perturbed functions. We then present an algorithm that checks whether a given bivariate function is a multi-unit assignment valuation, and if the answer is “yes,” computes a weighted bipartite graph representing the function.