List of Papers

List of Papers

Papers in Refereed Journals (<-- click to unfold/fold)
  1. Akiyoshi Shioura, Vitaly A. Strusevich, Natalia V. Shakhlevich:
    Generalizing Horn's Conditions for Preemptive Scheduling on Identical Parallel Machines via Network Flow Techniques
    Networks, to appear.
    DOI:

  2. Kazuo Murota, Akiyoshi Shioura:
    Note on Minimization of Quasi M♮-convex Functions
    Japan Journal of Industrial and Applied Mathematics, available online (2023).
    DOI: 10.1007/s13160-023-00633-3 (open access)

  3. Takafumi Otsuka, Akiyoshi Shioura:
    Characterization and algorithm for bivariate multi-unit assignment valuations
    Japan Journal of Industrial and Applied Mathematics, available online (2023).
    DOI: 10.1007/s13160-023-00597-4 (open access)

  4. Akiyoshi Shioura, Vitaly A. Strusevich, Natalia V. Shakhlevich:
    Preemptive scheduling of parallel jobs of two sizes with controllable processing times
    Journal of Scheduling , available online (2023).
    DOI: 10.1007/s10951-023-00782-w (open access)

  5. Akiyoshi Shioura:
    M-convex function minimization under L1-distance constraint and its application to dock re-allocation in bike sharing system
    Mathematics of Operations Research, 47 (2) (2022), 1566-1611.
    DOI: 10.1287/moor.2021.1180
    arXiv version

  6. Norito Minamikawa, Akiyoshi Shioura:
    Time bounds of basic steepest descent algorithms for M-convex function minimization and related problems
    Journal of Operations Research Society of Japan, 64 (2021), 45-60. (open access)
    DOI: 10.15807/jorsj.64.45

  7. Yusei Fujimori, Yasushi Kawase, Tomomi Matsui, Akiyoshi Shioura:
    A fast algorithm for multiprocessor speed-scaling problem minimizing completion time and energy consumption
    Information Processing Letters, 162 (2020), Article 105991.
    DOI: 10.1016/j.ipl.2020.105991

  8. Norito Minamikawa, Akiyoshi Shioura:
    Separable convex resource allocation problem with L1-distance constraint
    Journal of Operations Research Society of Japan, 62 (2019), 109-120. (open access)
    DOI: 10.15807/jorsj.62.109

  9. Akiyoshi Shioura, Natalia V. Shakhlevich, Vitaly A. Strusevich :
    Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost
    Journal of Global Optimization , 76 (2020), 471-490. (open access)
    DOI: 10.1007/s10898-018-0686-2

  10. Akiyoshi Shioura, Natalia V. Shakhlevich, and Vitaly A. Strusevich, Bernhard Primas:
    Models and algorithms for energy-efficient scheduling with immediate start of jobs
    Journal of Scheduling , 21 (2018), 505-516. (open access)
    DOI: 10.1007/s10951-017-0552-y

  11. Akiyoshi Shioura:
    On the Partnership Formation Problem
    Journal of Mechanism and Institution Design, 2 (2017), 105-140. (open access)
    DOI: 10.22574/jmid.2017.12.004

  12. Kazuo Murota, Akiyoshi Shioura:
    Simpler Exchange Axioms for M-concave Functions on Generalized Polymatroids
    Japan Journal of Industrial and Applied Mathematics, 35 (2017), 235-259.
    DOI: 10.1007/s13160-017-0285-5
    working paper

  13. Kazuo Murota, Akiyoshi Shioura:
    On Equivalence of M^\natural-concavity of a Set Function and Submodularity of its Conjugate
    Journal of Operations Research Society of Japan, 61 (2018), 163-171. (open access)
    DOI: 10.15807/jorsj.61.163

  14. Akiyoshi Shioura, Natalia V. Shakhlevich, and Vitaly A. Strusevich :
    Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches
    European Journal of Operational Research, 266 (2018), 795-818. (open access)
    DOI: 10.1016/j.ejor.2017.08.034

  15. Shun Fukuda, Akiyoshi Shioura, Takeshi Tokuyama:
    Buyback problem with discrete concave valuation functions
    Discrete Optimization, 26 (2017), 78-96.
    DOI: 10.1016/j.disopt.2017.07.002
    preprint

  16. Kazuo Murota, Akiyoshi Shioura:
    Note on time bounds of two-phase algorithms for L-convex function minimization
    Japan Journal of Industrial and Applied Mathematics, 34 (2017), 429-440.
    DOI: 10.1007/s13160-017-0246-z
    working paper

  17. Akiyoshi Shioura, Natalia V. Shakhlevich, and Vitaly A. Strusevich :
    Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints
    INFORMS Journal on Computing, 29 (2017), 724-736. (open access)
    DOI: 10.1287/ijoc.2017.0758

  18. Akiyoshi Shioura:
    Algorithms for L-convex Function Minimization: Connection Between Discrete Convex Analysis and Other Research Fields
    Journal of Operations Research Society of Japan, 60 (3) (2017), 216-243. (open access)
    DOI: 10.15807/jorsj.60.216
    working paper

  19. Kazuo Murota, Akiyoshi Shioura, Zaifu Yang:
    Time Bounds for Iterative Auctions: A Unified Approach by Discrete Convex Analysis
    Discrete Optimization, 19 (2016), 36-62.
    DOI: 10.1016/j.disopt.2016.01.001
    preprint

  20. Ferran Hurtado, Matias Korman, Marc van Kreveld, Maarten Löffler, Vera Sacristán, Akiyoshi Shioura, Rodrigo I. Silveira, Bettina Speckmann, and Takeshi Tokuyama:
    Colored Spanning Graphs for Set Visualization
    Computational Geometry, 68 (2018), 262-276.
    DOI: 10.1016/j.comgeo.2017.06.006
    preprint at arXiv

  21. Akiyoshi Shioura and Zaifu Yang:
    Equilibrium, Auction, and Generalized Gross Substitutes and Complements
    Journal of Operations Research Society of Japan, 58 (4) (2015), 410-435. (open access)
    DOI: 10.15807/jorsj.58.410
    pdf

  22. Yoshiko T. Ikebe, Yosuke Sekiguchi, Akiyoshi Shioura, and Akihisa Tamura:
    Stability and Competitive Equilibria in Multi-unit Trading Networks with Discrete Concave Utility Functions
    Japan Journal of Industrial and Applied Mathematics, 32 (2) (2015), 373-410.
    DOI: 10.1007/s13160-015-0175-7
    pdf file

  23. Akiyoshi Shioura, Natalia V. Shakhlevich, and Vitaly A. Strusevich :
    Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines
    INFORMS Journal on Computing , 28 (1) (2016), 148-161. (open access)
    DOI: 10.1287/ijoc.2015.0660
    pdf file

  24. Satoru Fujishige, Kazuo Murota, and Akiyoshi Shioura:
    Monotonicity in Steepest Ascent Algorithms for Polyhedral L-Concave Functions
    Journal of Operations Research Society of Japan, 58 (2) (2015), 184-208. (open access)
    DOI: 10.15807/jorsj.58.184
    pdf

  25. Akiyoshi Shioura and Akihisa Tamura :
    Gross Substitutes Condition and Discrete Concavity for Multi-Unit Valuations: A Survey
    Journal of Operations Research Society of Japan, 58 (1) (2015), 61-103. (open access)
    DOI: 10.15807/jorsj.58.61
    pdf

  26. Akiyoshi Shioura, Natalia V. Shakhlevich, and Vitaly A. Strusevich :
    Decomposition Algorithms for Submodular Optimization with Applications to Parallel Machine Scheduling with Controllable Processing Times
    Mathematical Programming, 153 (2) (2015), 495-534. (open access)
    DOI: 10.1007/s10107-014-0814-9

  27. Kazuo Murota and Akiyoshi Shioura:
    Exact Bounds for Steepest Descent Algorithms of L-convex Function Minimization
    Operations Research Letters, 42 (5) (2014), 361-366.
    DOI: 10.1016/j.orl.2014.06.005
    pdf file

  28. Akiyoshi Shioura :
    Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility under Budget Constraints
    Mathematics of Operations Research, 40 (1) (2015), 171-191.
    DOI: 10.1287/moor.2014.0668
    pdf file

  29. Jinhee Chun, Akiyoshi Shioura, Truong Minh Tien, and Takeshi Tokuyama:
    A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E97-A (6) (2014), 1220-1230.
    DOI: not available
    pdf file

  30. Kazuo Murota and Akiyoshi Shioura:
    Dijkstra's Algorithm and L-concave Function Maximization
    Mathematical Programming, 145 (1-2) (2014), 163-177.
    DOI: 10.1007/s10107-013-0643-2
    pdf file

  31. Akiyoshi Shioura, Natalia V. Shakhlevich, and Vitaly A. Strusevich :
    A Submodular Optimization Approach to Bicriteria Scheduling Problems with Controllable Processing Times on Parallel Machines
    SIAM Journal on Discrete Mathematics, 27 (1) (2013), 186-204.
    DOI: 10.1137/110843836
    pdf file

  32. Akiyoshi Shioura:
    Matroid Rank Functions and Discrete Concavity
    Japan Journal of Industrial and Applied Mathematics, 29 (3) (2012), 535-546.
    DOI: 10.1007/s13160-012-0082-0
    pdf file

  33. Akiyoshi Shioura, Shunya Suzuki:
    Optimal Allocation Problem with Quadratic Utility Functions and Its Relationship with Graph Cut Problem
    Journal of Operations Research Society of Japan, 55 (1) (2012), 92-105. (open access)
    DOI: not available
    pdf file

  34. Akiyoshi Shioura :
    Neighbor Systems, Jump Systems, and Bisubmodular Polyhedra
    SIAM Journal on Discrete Mathematics, 26 (1) (2012), 114-144.
    DOI:10.1137/110831684
    pdf file

  35. Satoko Moriguchi, Akiyoshi Shioura, Nobuyuki Tsuchimura:
    M-convex Function Minimization by Continuous Relaxation Approach ---Proximity Theorem and Algorithm---
    SIAM Journal on Optimization, 21 (3) (2011), 633-668 .
    DOI:10.1137/080736156
    pdf file

  36. Akiyoshi Shioura, Mutsunori Yagiura:
    A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions
    Journal of Graph Algorithms and Applications, 14 (2) (2010), 391-407.
    pdf file

  37. Vladimir Kolmogorov and Akiyoshi Shioura:
    New Algorithms for Convex Cost Tension Problem with Application to Computer Vision
    Discrete Optimization, 6 (4) (2009), 378-393.
    pdf file

  38. Akiyoshi Shioura:
    On the Pipage Rounding Algorithm for Submodular Function Maximization ---A View from Discrete Convex Analysis---
    Discrete Mathematics, Algorithms and Applications, 1 (1) (2009), 1-23.
    pdf file

  39. Natalia V. Shakhlevich, Akiyoshi Shioura, and Vitaly A. Strusevich :
    Single Machine Scheduling with Controllable Processing Times by Submodular Optimization
    International Journal of Foundations of Computer Science, 20 (2) (2009), 247-269.
    pdf file

  40. Kazuo Murota and Akiyoshi Shioura:
    Note on the Continuity of M-convex and L-convex Functions in Continuous Variables
    Journal of the Operations Research Society of Japan 51 (4) (2008), 265-273.
    pdf file

  41. Akiyoshi Shioura and Ken'ichiro Tanaka:
    Polynomial-time Algorithms for Linear and Convex Optimization on Jump Systems
    SIAM Journal on Discrete Mathematics, 21 (2) (2007), 504-522.
    DOI: 10.1137/060656899
    pdf file.

  42. Akiyoshi Shioura and Takeshi Tokuyama:
    Efficiently Pricing European-Asian Options: Ultimate Implementation and Analysis of the AMO Algorithm
    Information Processing Letters 100 (6) (2006), 213-219.
    pdf file.

  43. Akiyoshi Shioura, Ning Sun, and Zaifu Yang:
    Efficient Strategy Proof Fair Allocation Algorithms
    Journal of the Operations Research Society of Japan 49 (2) (2006), 144-150.
    pdf file.

  44. Kazuo Murota and Akiyoshi Shioura:
    Substitutes and Complements in Network Flows Viewed as Discrete Convexity
    Discrete Optimization 2 (2005), 256-268.
    DOI: 10.1016/j.disopt.2005.04.002
    pdf file.

  45. Ken'ichiro Ohta, Kunihiko Sadakane, Akiyoshi Shioura, and Takeshi Tokuyama:
    A Fast, Accurate and Simple Method for Pricing European-Asian and Saving-Asian Options
    Algorithmica 42 (2005), 141 - 158
    pdf file.

  46. Rashid Farooq and Akiyoshi Shioura:
    A Note on the Equivalence Between Substitutability and M$^\natural$-convexity
    Pacific Journal of Optimization 1 (2005), 243-252
    pdf file.

  47. Kazuo Murota and Akiyoshi Shioura:
    Quadratic M-convex and L-convex Functions
    Advances in Applied Mathematics 33 (2004) 318-341.
    pdf file.

  48. Kazuo Murota and Akiyoshi Shioura:
    Conjugacy Relationship between M-convex and L-convex Functions in Continuous Variables
    Mathematical Programming 101 (2004), 415-433.
    pdf file.

  49. Satoko Moriguchi and Akiyoshi Shioura:
    On Hochbaum's Proximity-Scaling Algorithm for the General Resource Allocation Problem
    Mathematics of Operations Research, 29 (2004) 394-397.
    pdf file.

  50. Kazuo Murota and Akiyoshi Shioura:
    Fundamental Properties of M-convex and L-convex Functions in Continuous Variables
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E87-A (2004) 1042-1052.
    pdf file.

  51. Akiyoshi Shioura:
    The MA-Ordering Max-Flow Algorithm is Not Strongly Polynomial for Directed Networks
    Operations Research Letters 32 (2004) 31-35.
    pdf file.

  52. Akiyoshi Shioura:
    Fast Scaling Algorithms for M-convex Function Minimization with Application to the Resource Allocation Problem
    Discrete Applied Mathematics 134 (2004) 303-316
    pdf file.

  53. Kazuo Murota and Akiyoshi Shioura:
    Quasi M-convex and L-convex Functions: Quasiconvexity in Discrete Optimization
    Discrete Applied Mathematics 131 (2003) 467-494
    pdf file.

  54. Satoko Moriguchi, Kazuo Murota, and Akiyoshi Shioura:
    Scaling Algorithms for M-convex Function Minimization
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E85-A (2002) 922-929.
    pdf file.

  55. Kazuo Murota and Akiyoshi Shioura:
    Relationship of M-/L-convex Functions with Discrete Convex Functions by Miller and by Favati-Tardella
    Discrete Applied Mathematics 115 (2001) 151-176.
    pdf file.

  56. Kazuo Murota and Akiyoshi Shioura:
    Extension of M-convexity and L-convexity to Polyhedral Convex Functions
    Advances in Applied Mathematics 25 (2000) 352-427.
    pdf file.

  57. S. Thomas McCormick and Akiyoshi Shioura:
    Minimum Ratio Canceling is Oracle Polynomial for Linear Programming, but Not Strongly Polynomial, Even for Networks
    Operations Research Letters 27 (2000) 199-207.
    pdf file.

  58. Akiyoshi Shioura:
    Level Set Characterization of M-convex Functions
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E83-A (2000) 586-589.
    pdf file.

  59. Kazuo Murota and Akiyoshi Shioura:
    M-Convex Function on Generalized Polymatroid
    Mathematics of Operations Research, 24 (1999) 95-105. [Errata and Supplements]
    DOI: 10.1287/moor.24.1.95
    pdf file.

  60. Akiyoshi Shioura:
    Minimization of an M-convex Function
    Discrete Applied Mathematics 84 (1998) 215-220.
    pdf file.
    program implemented in C.

  61. Akiyoshi Shioura:
    A Constructive Proof for the Induction of M-convex Functions through Networks
    Discrete Applied Mathematics 82 (1998) 271-278.
    pdf file.

  62. Akiyoshi Shioura and Maiko Shigeno:
    The Tree Center Problems and the Relationships with the Bottleneck Knapsack Problems
    Networks 29 (1997), 29 (2), 107-110.
    DOI: 10.1002/(SICI)1097-0037(199703)29:2<107::AID-NET4>3.0.CO;2-N
    pdf file.

  63. Akiyoshi Shioura and Takeaki Uno:
    A Linear Time Algorithm for Finding a k-Tree Core
    Journal of Algorithms 23 (1997) 281-290.
    pdf file.

  64. Akiyoshi Shioura, Akihisa Tamura , and Takeaki Uno:
    An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
    SIAM Journal on Computing 26 (1997) 678-692.
    pdf file.
    program implemented in C.

  65. Akiyoshi Shioura, Akihisa Tamura :
    Efficiently Scanning All Spanning Trees of an Undirected Graph
    Journal of Operations Research Society in Japan 38 (1995), 331-344.
    pdf file.

Papers in Refereed Conferences (<-- click to unfold/fold)
  1. Shun Fukuda, Akiyoshi Shioura, Takeshi Tokuyama:
    Buyback Problem with Discrete Concave Valuation Functions
    Proceedings of the 13th International Workshop on Approximation and Online Algorithms (WAOA 2015) ,
    Lecture Notes in Computer Science 9499, Springer (2015), 72-83.

  2. Kazuo Murota, Akiyoshi Shioura, Zaifu Yang:
    Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items
    Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013),
    Lecture Notes in Computer Science 8283, Springer (2013), 468-478.
    Extended abstract: pdf file.
    METR Technical Report (with appendix) pdf file (revised version) .

  3. Akiyoshi Shioura :
    Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility under Budget Constraints
    Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011),
    Lecture Notes in Computer Science 6942, Springer (2011), 1-12.
    Extended abstract: pdf file.

  4. Akiyoshi Shioura, Shunya Suzuki:
    Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions
    Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011),
    Lecture Notes in Computer Science 6648, Springer (2011), 142-153.
    Extended abstract: pdf file.

  5. Akiyoshi Shioura :
    Neighbor Systems, Jump Systems, and Bisubmodular Polyhedra
    Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010),
    Lecture Notes in Computer Science 6506, Springer (2010), 169-181.
    Extended abstract: pdf file.

  6. Akiyoshi Shioura and Mutsunori Yagiura:
    A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions
    Proceedings of the 15th International Computing and Combinatorics Conference (COCOON 2009),
    Lecture Notes in Computer Science 5609, Springer (2009), 116-126.
    Extended abstract: pdf file.

  7. Natalia Shakhlevich, Akiyoshi Shioura, and Vitaly Strusevich:
    Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times: A Polymatroid Optimization Approach
    Proceedings of the 16th Annual European Symposium on Algorithms (ESA 2008),
    Lecture Notes in Computer Science 5193, Springer (2008), 756-767.
    Extended abstract: pdf file.

  8. Akiyoshi Shioura, and Takeshi Tokuyama:
    Efficiently Pricing European-Asian Options: Ultimate Implementation and Analysis of the AMO Algorithm
    Proceedings of the 1st International Conference on Algorithmic Applications in Management (AAIM 2005),
    Lecture Notes in Computer Science 3521, Springer (2005) 291-300.
    Extended abstract: ps file, pdf file.

  9. Ken'ichiro Ohta, Kunihiko Sadakane, Akiyoshi Shioura, and Takeshi Tokuyama:
    A Fast, Accurate and Simple Method for Pricing European-Asian and Saving-Asian Options
    Proceedings of 10th Annual European Symposium on Algorithms (ESA 2002),
    Lecture Notes in Computer Science 2461, Springer (2002) 772-784.
    Extended abstract: ps file, pdf file.

  10. S. Thomas McCormick and Akiyoshi Shioura:
    Minimum Ratio Canceling is Oracle Polynomial for Linear Programming, but Not Strongly Polynomial, Even for Networks
    Proceedings of 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 200),
    944-952.
    Extended abstract: ps file, pdf file.

Technical Reports, etc. (<-- click to unfold/fold)
  1. 塩浦昭義:
    「組合せ最適化のアルゴリズムと離散凸解析」
    オペレーションズ・リサーチ 58 (6) (2013) 332-338.

  2. 塩浦昭義:
    「離散凸関数はどのような性質を満たすべきか：離散最適化の視点から」
    オペレーションズ・リサーチ 47(11) (2002) 730-736.
    ps file, pdf file.

  3. Kazuo Murota and Akiyoshi Shioura:
    M-convex and L-convex Functions over the Real Space: Two Conjugate Classes of Combinatorial Convex Functions
    Technical Report METR2002-09, Dept. of Mathematical Engineering and Information Physics, University of Tokyo (2002).
    ps file, pdf file.

  4. Akiyoshi Shioura and Takeaki Uno:
    An O(n log n)-time Algorithm for an l-core of a Tree
    Research Report

  5. S. Thomas McCormick, Andreas S. Schulz, Akiyoshi Shioura, and Robert Weismantel:
    A Note on an Augmentation Method for Mixed Integer Programming Problems
    Working Paper OR348-00, Operations Research Center, Massachusetts Institute of Technology (2000).

  6. Akiyoshi Shioura:
    A Note on `2-Best Solutions under Distance Constraints: The Model and Exemplary Results for Matroids' by Althoefer and Wenzel
    Research Report 22, Dept. of Mechanical Engineering, Sophia Univerisity (1997).

  7. Akiyoshi Shioura:
    An Algorithmic Proof for the Induction of M-convex Functions through Networks
    Research Report B-317, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology (1996).
    ps file, pdf file.

  8. Akiyoshi Shioura and Maiko Shigeno:
    The Tree-Shaped Facility Location Problems and the Relationships with the Knapsack Problems
    Research Report B-300, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology (1995).
    ps file, pdf file.