List of Papers

Papers in Refereed Journals

  1. Satoru Fujishige, Kazuo Murota, and Akiyoshi Shioura:
    Monotonicity in Steepest Ascent Algorithms for Polyhedral L-Concave Functions
    Journal of Operations Research Society of Japan, to appear.
    pdf file

  2. 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.
    pdf file

  3. 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, to appear.
    DOI: 10.1007/s10107-014-0814-9

  4. 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

  5. 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

  6. 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.
    pdf file

  7. 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

  8. 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

  9. 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

  10. 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.
    pdf file

  11. 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

  12. 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

  13. 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

  14. 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

  15. 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

  16. 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

  17. 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

  18. 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.
    pdf file.

  19. 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.

  20. 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.

  21. 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.

  22. 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.

  23. 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.

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

  25. 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.

  26. 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.

  27. 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.

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

  29. 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.

  30. 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.

  31. 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.

  32. 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.

  33. 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.

  34. 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.

  35. 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.

  36. Kazuo Murota and Akiyoshi Shioura:
    M-Convex Function on Generalized Polymatroid
    Mathematics of Operations Research, 24 (1999) 95-105.
    pdf file.

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

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

  39. 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.

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

  41. 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.

  42. 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  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.