Satoru Fujishige

According to our database1, Satoru Fujishige authored at least 81 papers between 1972 and 2019.

Collaborative distances:



In proceedings 
PhD thesis 





Greedy systems of linear inequalities and lexicographically optimal solutions.
RAIRO - Operations Research, 2019

Submodular optimization views on the random assignment problem.
Math. Program., 2019

Preface: The fourth International Symposium on Combinatorial Optimization (ISCO) 2016.
J. Comb. Optim., 2019

A note on submodular function minimization by Chubanov's LP algorithm.
Discrete Optimization, 2019

A Note on a Nearly Uniform Partition into Common Independent Sets of Two Matroids.
CoRR, 2019

The Random Assignment Problem with Submodular Constraints on Goods.
ACM Trans. Economics and Comput., 2018

Polynomial combinatorial algorithms for skew-bisubmodular function minimization.
Math. Program., 2018

Matroids Are Immune to Braess' Paradox.
Math. Oper. Res., 2017

Parametric bisubmodular function minimization and its associated signed ring family.
Discrete Applied Mathematics, 2017

Random decentralized market processes for stable job matchings with competitive salaries.
J. Economic Theory, 2016

Congestion games viewed from M-convexity.
Oper. Res. Lett., 2015

Dual consistent systems of linear inequalities and cardinality constrained polytopes.
Math. Program., 2015

A Min-Max Theorem for Transversal Submodular Functions and Its Implications.
SIAM J. Discrete Math., 2014

Generalized skew bisubmodularity: A characterization and a min-max theorem.
Discrete Optimization, 2014

Bisubmodular polyhedra, simplicial divisions, and discrete convexity.
Discrete Optimization, 2014

A note on polylinking flow networks.
Math. Program., 2013

On the feasible payoff set of two-player repeated games with unequal discounting.
Int. J. Game Theory, 2013

Independent arborescences in directed graphs.
Discrete Mathematics, 2013

The root location problem for arc-disjoint arborescences.
Discrete Applied Mathematics, 2012

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization.
Math. Program., 2010

A note on disjoint arborescences.
Combinatorica, 2010

Lattice Polyhedra and Submodular Flows.
Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2010

Minimizing Continuous Extensions of Discrete Convex Functions with Linear Inequality Constraints.
SIAM Journal on Optimization, 2009

Minimum Transversals in Posimodular Systems.
SIAM J. Discrete Math., 2009

A general model for matroids and the greedy algorithm.
Math. Program., 2009

A Structure Theory for the Parametric Submodular Intersection Problem.
Math. Oper. Res., 2009

A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph.
Inf. Process. Lett., 2009

Minimizing a monotone concave function with laminar covering constraints.
Discrete Applied Mathematics, 2008

Minimum Cost Source Location Problems with Flow Requirements.
Algorithmica, 2008

Theory of Principal Partitions Revisited.
Proceedings of the Research Trends in Combinatorial Optimization, 2008

A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis.
Math. Oper. Res., 2007

Matroids on convex geometries (cg-matroids).
Discrete Mathematics, 2007

An O(n log2n) algorithm for the optimal sink location problem in dynamic tree networks.
Discrete Applied Mathematics, 2006

A general two-sided matching market with discrete concave utility functions.
Discrete Applied Mathematics, 2006

Minimum Transversals in Posi-modular Systems.
Proceedings of the Algorithms, 2006

Bisubmodular Function Minimization.
SIAM J. Discrete Math., 2005

Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2.
Discrete Mathematics, 2004

Dual greedy polyhedra, choice functions, and abstract convex geometries.
Discrete Optimization, 2004

An O(n log 2n) Algorithm for the Optimal Sink Location Problem in Dynamic Tree Networks.
Proceedings of the Exploring New Frontiers of Theoretical Informatics, 2004

A maximum flow algorithm using MA ordering.
Oper. Res. Lett., 2003

Source location problem with flow requirements in directed networks.
Optimization Methods and Software, 2003

Submodular function minimization and related topics.
Optimization Methods and Software, 2003

A Note on Kelso and Crawford's Gross Substitutes Condition.
Math. Oper. Res., 2003

A Generalized Gale-Shapley Algorithm for a Discrete-Concave Stable-Marriage Model.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

A descent method for submodular function minimization.
Math. Program., 2002

Locating Sources to Meet Flow Demands in Undirected Networks.
J. Algorithms, 2002

A simple matching algorithm for regular bipartite graphs.
Inf. Process. Lett., 2002

A combinatorial strongly polynomial algorithm for minimizing submodular functions.
J. ACM, 2001

Realization of set functions as cut functions of graphs and hypergraphs.
Discrete Mathematics, 2001

Notes on L-/M-convex functions and the separation theorems.
Math. Program., 2000

A note on Faigle and Kern's dual greedy polyhedra.
Math. Program., 2000

A laminarity property of the polyhedron described by a weakly posi-modular set function.
Discrete Applied Mathematics, 2000

A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Minimizing a Submodular Function Arising From a Concave Function.
Discrete Applied Mathematics, 1999

A Min-Max Theorem for Bisubmodular Polyhedra.
SIAM J. Discrete Math., 1997

On structures of bisubmodular polyhedra.
Math. Program., 1996

A characterization of bisubmodular functions.
Discrete Mathematics, 1996

Decomposition of a Bidirected Graph into Strongly Connected Components and Its Signed Poset Structure.
Discrete Applied Mathematics, 1996

A New Scaling Algorithm for the Maximum Mean Cut Problem.
Algorithmica, 1994

A note on the Frank-Tardos bi-truncation algorithm for crossing-submodular functions.
Math. Program., 1992

A Speculative Contraction Method for Minimum Cost Flows: Toward a Practical Algorithm.
Proceedings of the Network Flows And Matching, 1991

A Strongly Polynomial Algorithm for Minimum Cost Submodular Flow Problems.
Math. Oper. Res., 1989

Optimization over the polyhedron determined by a submodular function on a co-intersecting family.
Math. Program., 1988

The Fair Resource Allocation Problem with Submodular Constraints.
Math. Oper. Res., 1988

Finding a homotopy base for directed paths in an acyclic graph.
Discrete Applied Mathematics, 1987

An out-of-kilter method for submodular flows.
Discrete Applied Mathematics, 1987

A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm.
Math. Program., 1986

Book reviews.
Zeitschr. für OR, 1986

A decomposition of distributive lattices.
Discrete Mathematics, 1985

On the subdifferential of a submodular function.
Math. Program., 1984

Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions.
Math. Program., 1984

Structures of polyhedra determined by submodular functions on crossing families.
Math. Program., 1984

A note on Frank's generalized polymatroids.
Discrete Applied Mathematics, 1984

Canonical decompositions of symmetric submodular systems.
Discrete Applied Mathematics, 1983

A note on the problem of updating shortest paths.
Networks, 1981

Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector.
Math. Oper. Res., 1980

An Efficient PQ-Graph Algorithm for Solving the Graph-Realization Problem.
J. Comput. Syst. Sci., 1980

Principal structures of submodular systems.
Discrete Applied Mathematics, 1980

Polymatroidal Dependence Structure of a Set of Random Variables
Information and Control, October, 1978

Comments on "Optimal Control of Unreliable Dynamic Systems with Discrete Time Inspections".
IEEE Trans. Systems, Man, and Cybernetics, 1976

Sequential State Estimation with Interrupted Observation
Information and Control, August, 1972