Satoru Fujishige

According to our database, Satoru Fujishige authored at least 88 papers between 1972 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem.

Satoru Fujishige, Tomonari Kitahara, László A. Végh

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

2022

Discrete 2-convex functions.

Satoru Fujishige, Fabio Tardella

Math. Program., 2022

Minimizing submodular functions on diamonds via generalized fractional matroid matchings.

Satoru Fujishige, Tamás Király, Kazuhisa Makino, Kenjiro Takazawa, Shin-ichi Tanigawa

J. Comb. Theory B, 2022

Compression of M^♮-convex functions - Flag matroids and valuated permutohedra.

Satoru Fujishige, Hiroshi Hirai

J. Comb. Theory A, 2022

2021

Signed ring families and signed posets.

Kazutoshi Ando, Satoru Fujishige

Optim. Methods Softw., 2021

2019

Greedy systems of linear inequalities and lexicographically optimal solutions.

Satoru Fujishige

RAIRO Oper. Res., 2019

Submodular optimization views on the random assignment problem.

Satoru Fujishige, Yoshio Sano, Ping Zhan

Math. Program., 2019

Preface: The fourth International Symposium on Combinatorial Optimization (ISCO) 2016.

Satoru Fujishige, Ali Ridha Mahjoub, Franz Rendl

J. Comb. Optim., 2019

A note on submodular function minimization by Chubanov's LP algorithm.

Satoru Fujishige

Discret. Optim., 2019

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

Satoru Fujishige, Kenjiro Takazawa, Yu Yokoi

CoRR, 2019

2018

The Random Assignment Problem with Submodular Constraints on Goods.

Satoru Fujishige, Yoshio Sano, Ping Zhan

ACM Trans. Economics and Comput., 2018

Polynomial combinatorial algorithms for skew-bisubmodular function minimization.

Satoru Fujishige, Shin-ichi Tanigawa

Math. Program., 2018

2017

Matroids Are Immune to Braess' Paradox.

Satoru Fujishige, Michel X. Goemans, Tobias Harks, Britta Peis, Rico Zenklusen

Math. Oper. Res., 2017

Parametric bisubmodular function minimization and its associated signed ring family.

Satoru Fujishige

Discret. Appl. Math., 2017

2016

Random decentralized market processes for stable job matchings with competitive salaries.

Bo Chen, Satoru Fujishige, Zaifu Yang

J. Econ. Theory, 2016

2015

Congestion games viewed from M-convexity.

Satoru Fujishige, Michel X. Goemans, Tobias Harks, Britta Peis, Rico Zenklusen

Oper. Res. Lett., 2015

Dual consistent systems of linear inequalities and cardinality constrained polytopes.

Satoru Fujishige, Jens Maßberg

Math. Program., 2015

2014

A Min-Max Theorem for Transversal Submodular Functions and Its Implications.

Satoru Fujishige, Shin-ichi Tanigawa

SIAM J. Discret. Math., 2014

Generalized skew bisubmodularity: A characterization and a min-max theorem.

Satoru Fujishige, Shin-ichi Tanigawa, Yuichi Yoshida

Discret. Optim., 2014

Bisubmodular polyhedra, simplicial divisions, and discrete convexity.

Satoru Fujishige

Discret. Optim., 2014

2013

A note on polylinking flow networks.

Satoru Fujishige

Math. Program., 2013

On the feasible payoff set of two-player repeated games with unequal discounting.

Bo Chen, Satoru Fujishige

Int. J. Game Theory, 2013

Independent arborescences in directed graphs.

András Frank, Satoru Fujishige, Naoyuki Kamiyama, Naoki Katoh

Discret. Math., 2013

2012

The root location problem for arc-disjoint arborescences.

Satoru Fujishige, Naoyuki Kamiyama

Discret. Appl. Math., 2012

2010

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization.

S. Thomas McCormick, Satoru Fujishige

Math. Program., 2010

A note on disjoint arborescences.

Satoru Fujishige

Comb., 2010

Lattice Polyhedra and Submodular Flows.

Satoru Fujishige, Britta Peis

Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2010

2009

Minimizing Continuous Extensions of Discrete Convex Functions with Linear Inequality Constraints.

Satoru Fujishige, Takumi Hayashi, Kiyohito Nagano

SIAM J. Optim., 2009

Minimum Transversals in Posimodular Systems.

Mariko Sakashita, Kazuhisa Makino, Hiroshi Nagamochi, Satoru Fujishige

SIAM J. Discret. Math., 2009

A general model for matroids and the greedy algorithm.

Ulrich Faigle, Satoru Fujishige

Math. Program., 2009

A Structure Theory for the Parametric Submodular Intersection Problem.

Satoru Fujishige, Kiyohito Nagano

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.

Kristóf Bérczi, Satoru Fujishige, Naoyuki Kamiyama

Inf. Process. Lett., 2009

2008

Minimizing a monotone concave function with laminar covering constraints.

Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige

Discret. Appl. Math., 2008

Minimum Cost Source Location Problems with Flow Requirements.

Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige

Algorithmica, 2008

Theory of Principal Partitions Revisited.

Satoru Fujishige

Proceedings of the Research Trends in Combinatorial Optimization, 2008

2007

A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis.

Satoru Fujishige, Akihisa Tamura

Math. Oper. Res., 2007

Matroids on convex geometries (cg-matroids).

Satoru Fujishige, Gleb A. Koshevoy, Yoshio Sano

Discret. Math., 2007

2006

An O(n log²n) algorithm for the optimal sink location problem in dynamic tree networks.

Satoko Mamada, Takeaki Uno, Kazuhisa Makino, Satoru Fujishige

Discret. Appl. Math., 2006

A general two-sided matching market with discrete concave utility functions.

Satoru Fujishige, Akihisa Tamura

Discret. Appl. Math., 2006

Minimum Transversals in Posi-modular Systems.

Mariko Sakashita, Kazuhisa Makino, Hiroshi Nagamochi, Satoru Fujishige

Proceedings of the Algorithms, 2006

2005

Bisubmodular Function Minimization.

Satoru Fujishige, Satoru Iwata

SIAM J. Discret. Math., 2005

2004

Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2.

Satoru Fujishige, Kazuhisa Makino, Takashi Takabatake, Kenji Kashiwabara

Discret. Math., 2004

Dual greedy polyhedra, choice functions, and abstract convex geometries.

Satoru Fujishige

Discret. Optim., 2004

An O(n log 2n) Algorithm for the Optimal Sink Location Problem in Dynamic Tree Networks.

Satoko Mamada, Takeaki Uno, Kazuhisa Makino, Satoru Fujishige

Proceedings of the Exploring New Frontiers of Theoretical Informatics, 2004

2003

A maximum flow algorithm using MA ordering.

Satoru Fujishige

Oper. Res. Lett., 2003

Source location problem with flow requirements in directed networks.

Hiro Ito, Kazuhisa Makino, Kouji Arata, Shoji Honami, Yuichiro Itatsu, Satoru Fujishige

Optim. Methods Softw., 2003

Submodular function minimization and related topics.

Satoru Fujishige

Optim. Methods Softw., 2003

A Note on Kelso and Crawford's Gross Substitutes Condition.

Satoru Fujishige, Zaifu Yang

Math. Oper. Res., 2003

A Generalized Gale-Shapley Algorithm for a Discrete-Concave Stable-Marriage Model.

Akinobu Eguchi, Satoru Fujishige, Akihisa Tamura

Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

2002

A descent method for submodular function minimization.

Satoru Fujishige, Satoru Iwata

Math. Program., 2002

Locating Sources to Meet Flow Demands in Undirected Networks.

Kouji Arata, Satoru Iwata, Kazuhisa Makino, Satoru Fujishige

J. Algorithms, 2002

A simple matching algorithm for regular bipartite graphs.

Kazuhisa Makino, Takashi Takabatake, Satoru Fujishige

Inf. Process. Lett., 2002

Optimal Sink Location Problem for Dynamic Flows in a Tree Network.

Satoko Mamada, Kazuhisa Makino, Satoru Fujishige

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2002

2001

A combinatorial strongly polynomial algorithm for minimizing submodular functions.

Satoru Iwata, Lisa Fleischer, Satoru Fujishige

J. ACM, 2001

Realization of set functions as cut functions of graphs and hypergraphs.

Satoru Fujishige, Sachin B. Patkar

Discret. Math., 2001

2000

Notes on L-/M-convex functions and the separation theorems.

Satoru Fujishige, Kazuo Murota

Math. Program., 2000

A note on Faigle and Kern's dual greedy polyhedra.

Satoru Fujishige

Math. Program., 2000

A laminarity property of the polyhedron described by a weakly posi-modular set function.

Satoru Fujishige

Discret. Appl. Math., 2000

A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions.

Satoru Iwata, Lisa Fleischer, Satoru Fujishige

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999

Minimizing a Submodular Function Arising From a Concave Function.

Satoru Fujishige, Satoru Iwata

Discret. Appl. Math., 1999

1997

A Min-Max Theorem for Bisubmodular Polyhedra.

Satoru Fujishige

SIAM J. Discret. Math., 1997

1996

On structures of bisubmodular polyhedra.

Kazutoshi Ando, Satoru Fujishige

Math. Program., 1996

A characterization of bisubmodular functions.

Kazutoshi Ando, Satoru Fujishige, Takeshi Naitoh

Discret. Math., 1996

Decomposition of a Bidirected Graph into Strongly Connected Components and Its Signed Poset Structure.

Kazutoshi Ando, Satoru Fujishige, Toshio Nemoto

Discret. Appl. Math., 1996

1994

A New Scaling Algorithm for the Maximum Mean Cut Problem.

Kazuo Iwano, Shinji Misono, Shu Tezuka, Satoru Fujishige

Algorithmica, 1994

1992

A note on the Frank-Tardos bi-truncation algorithm for crossing-submodular functions.

Takeshi Naitoh, Satoru Fujishige

Math. Program., 1992

1991

A Speculative Contraction Method for Minimum Cost Flows: Toward a Practical Algorithm.

Satoru Fujishige, Kazuo Iwano, J. Nakano, Shu Tezuka

Proceedings of the Network Flows And Matching, 1991

1989

A Strongly Polynomial Algorithm for Minimum Cost Submodular Flow Problems.

Satoru Fujishige, Hans Röck, Uwe Zimmermann

Math. Oper. Res., 1989

1988

Optimization over the polyhedron determined by a submodular function on a co-intersecting family.

Satoru Fujishige

Math. Program., 1988

The Fair Resource Allocation Problem with Submodular Constraints.

Satoru Fujishige, Naoki Katoh, Tetsuo Ichimori

Math. Oper. Res., 1988

1987

Finding a homotopy base for directed paths in an acyclic graph.

Kazuo Murota, Satoru Fujishige

Discret. Appl. Math., 1987

An out-of-kilter method for submodular flows.

Satoru Fujishige

Discret. Appl. Math., 1987

1986

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

Satoru Fujishige

Math. Program., 1986

Book reviews.

David F. Shanno, A. J. J. Talman, Satoru Fujishige, Steven Nahmias, Karl Straßner, Götz Uebe

Z. Oper. Research, 1986

1985

A decomposition of distributive lattices.

Satoru Fujishige

Discret. Math., 1985

1984

On the subdifferential of a submodular function.

Satoru Fujishige

Math. Program., 1984

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

Satoru Fujishige

Math. Program., 1984

Structures of polyhedra determined by submodular functions on crossing families.

Satoru Fujishige

Math. Program., 1984

A note on Frank's generalized polymatroids.

Satoru Fujishige

Discret. Appl. Math., 1984

1983

Canonical decompositions of symmetric submodular systems.

Satoru Fujishige

Discret. Appl. Math., 1983

1981

A note on the problem of updating shortest paths.

Satoru Fujishige

Networks, 1981

1980

Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector.

Satoru Fujishige

Math. Oper. Res., 1980

An Efficient PQ-Graph Algorithm for Solving the Graph-Realization Problem.

Satoru Fujishige

J. Comput. Syst. Sci., 1980

Principal structures of submodular systems.

Satoru Fujishige

Discret. Appl. Math., 1980

1978

Polymatroidal Dependence Structure of a Set of Random Variables

Satoru Fujishige

Inf. Control., October, 1978

1976

Comments on "Optimal Control of Unreliable Dynamic Systems with Discrete Time Inspections".

Satoru Fujishige

IEEE Trans. Syst. Man Cybern., 1976

1974

Remarks on "optimal stochastic control for discrete-time linear system with interrupted observations".

Satoru Fujishige

Autom., 1974

1972

Sequential State Estimation with Interrupted Observation

Yoshikazu Sawaragi, T. Katayama, Satoru Fujishige

Inf. Control., August, 1972