Satoru Fujishige

Publication Activity (10 Years)

Years Active: 1972-2023
Publications (10 Years): 15

Top Topics

Submodular Functions

Top Venues

Discret. Optim.

Publications

Satoru Fujishige, Tomonari Kitahara, László A. Végh
An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem. IPCO (2023)
Satoru Fujishige, Tamás Király, Kazuhisa Makino, Kenjiro Takazawa, Shin-ichi Tanigawa
Minimizing submodular functions on diamonds via generalized fractional matroid matchings. J. Comb. Theory, Ser. B 157 (2022)
Satoru Fujishige, Hiroshi Hirai
-convex functions - Flag matroids and valuated permutohedra. J. Comb. Theory, Ser. A 185 (2022)
Satoru Fujishige, Fabio Tardella
Discrete 2-convex functions. Math. Program. 195 (1) (2022)
Kazutoshi Ando, Satoru Fujishige
Signed ring families and signed posets. Optim. Methods Softw. 36 (2-3) (2021)
Satoru Fujishige, Kenjiro Takazawa, Yu Yokoi
A Note on a Nearly Uniform Partition into Common Independent Sets of Two Matroids. CoRR (2019)
Satoru Fujishige, Yoshio Sano, Ping Zhan
Submodular optimization views on the random assignment problem. Math. Program. 178 (1-2) (2019)
Satoru Fujishige
Greedy systems of linear inequalities and lexicographically optimal solutions. RAIRO Oper. Res. 53 (5) (2019)
Satoru Fujishige, Ali Ridha Mahjoub, Franz Rendl
Preface: The fourth International Symposium on Combinatorial Optimization (ISCO) 2016. J. Comb. Optim. 37 (1) (2019)
Satoru Fujishige
A note on submodular function minimization by Chubanov's LP algorithm. Discret. Optim. 33 (2019)
Satoru Fujishige, Yoshio Sano, Ping Zhan
The Random Assignment Problem with Submodular Constraints on Goods. ACM Trans. Economics and Comput. 6 (1) (2018)
Satoru Fujishige, Shin-ichi Tanigawa
Polynomial combinatorial algorithms for skew-bisubmodular function minimization. Math. Program. 171 (1-2) (2018)
Satoru Fujishige
Parametric bisubmodular function minimization and its associated signed ring family. Discret. Appl. Math. 227 (2017)
Satoru Fujishige, Michel X. Goemans, Tobias Harks, Britta Peis, Rico Zenklusen
Matroids Are Immune to Braess' Paradox. Math. Oper. Res. 42 (3) (2017)
Bo Chen, Satoru Fujishige, Zaifu Yang
Random decentralized market processes for stable job matchings with competitive salaries. J. Econ. Theory 165 (2016)
Satoru Fujishige, Michel X. Goemans, Tobias Harks, Britta Peis, Rico Zenklusen
Congestion games viewed from M-convexity. Oper. Res. Lett. 43 (3) (2015)
Satoru Fujishige, Michel X. Goemans, Tobias Harks, Britta Peis, Rico Zenklusen
Matroids are Immune to Braess Paradox. CoRR (2015)
Satoru Fujishige, Jens Maßberg
Dual consistent systems of linear inequalities and cardinality constrained polytopes. Math. Program. 150 (1) (2015)
Satoru Fujishige, Shin-ichi Tanigawa, Yuichi Yoshida
Generalized skew bisubmodularity: A characterization and a min-max theorem. Discret. Optim. 12 (2014)
Satoru Fujishige, Shin-ichi Tanigawa
A Min-Max Theorem for Transversal Submodular Functions and Its Implications. SIAM J. Discret. Math. 28 (4) (2014)
Satoru Fujishige
Bisubmodular polyhedra, simplicial divisions, and discrete convexity. Discret. Optim. 12 (2014)
András Frank, Satoru Fujishige, Naoyuki Kamiyama, Naoki Katoh
Independent arborescences in directed graphs. Discret. Math. 313 (4) (2013)
Bo Chen, Satoru Fujishige
On the feasible payoff set of two-player repeated games with unequal discounting. Int. J. Game Theory 42 (1) (2013)
Satoru Fujishige
A note on polylinking flow networks. Math. Program. 137 (1-2) (2013)
Satoru Fujishige, Jens Maßberg
Dual Consistent Systems of Linear Inequalities and Cardinality Constrained Polytopes. ISCO (2012)
Satoru Fujishige, Naoyuki Kamiyama
The root location problem for arc-disjoint arborescences. Discret. Appl. Math. 160 (13-14) (2012)
Satoru Fujishige, Britta Peis
Lattice Polyhedra and Submodular Flows. CTW (2010)
S. Thomas McCormick, Satoru Fujishige
Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization. Math. Program. 122 (1) (2010)
Satoru Fujishige
A note on disjoint arborescences. Comb. 30 (2) (2010)
Satoru Fujishige, Takumi Hayashi, Kiyohito Nagano
Minimizing Continuous Extensions of Discrete Convex Functions with Linear Inequality Constraints. SIAM J. Optim. 20 (2) (2009)
Satoru Fujishige, Kiyohito Nagano
A Structure Theory for the Parametric Submodular Intersection Problem. Math. Oper. Res. 34 (3) (2009)
Ulrich Faigle, Satoru Fujishige
A general model for matroids and the greedy algorithm. Math. Program. 119 (2) (2009)
Kristóf Bérczi, Satoru Fujishige, Naoyuki Kamiyama
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. 109 (23-24) (2009)
Mariko Sakashita, Kazuhisa Makino, Hiroshi Nagamochi, Satoru Fujishige
Minimum Transversals in Posimodular Systems. SIAM J. Discret. Math. 23 (2) (2009)
Satoru Fujishige
Theory of Principal Partitions Revisited. Bonn Workshop of Combinatorial Optimization (2008)
S. Thomas McCormick, Satoru Fujishige
Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization. SODA (2008)
Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige
Minimizing a monotone concave function with laminar covering constraints. Discret. Appl. Math. 156 (11) (2008)
Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige
Minimum Cost Source Location Problems with Flow Requirements. Algorithmica 50 (4) (2008)
Satoru Fujishige, Akihisa Tamura
A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis. Math. Oper. Res. 32 (1) (2007)
Satoru Fujishige, Gleb A. Koshevoy, Yoshio Sano
Matroids on convex geometries (cg-matroids). Discret. Math. 307 (15) (2007)
Mariko Sakashita, Kazuhisa Makino, Hiroshi Nagamochi, Satoru Fujishige
Minimum Transversals in Posi-modular Systems. ESA (2006)
Satoru Fujishige, Akihisa Tamura
A general two-sided matching market with discrete concave utility functions. Discret. Appl. Math. 154 (6) (2006)
Satoko Mamada, Takeaki Uno, Kazuhisa Makino, Satoru Fujishige
n) algorithm for the optimal sink location problem in dynamic tree networks. Discret. Appl. Math. 154 (16) (2006)
Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige
Minimum Cost Source Location Problems with Flow Requirements. LATIN (2006)
Satoru Fujishige, Satoru Iwata
Bisubmodular Function Minimization. SIAM J. Discret. Math. 19 (4) (2005)
Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige
Minimizing a Monotone Concave Function with Laminar Covering Constraints. ISAAC (2005)
Satoko Mamada, Takeaki Uno, Kazuhisa Makino, Satoru Fujishige
An O(n log 2n) Algorithm for the Optimal Sink Location Problem in Dynamic Tree Networks. IFIP TCS (2004)
Satoru Fujishige, Kazuhisa Makino, Takashi Takabatake, Kenji Kashiwabara
Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2. Discret. Math. 280 (1-3) (2004)
Satoru Fujishige
Dual greedy polyhedra, choice functions, and abstract convex geometries. Discret. Optim. 1 (1) (2004)
Satoru Fujishige
Submodular function minimization and related topics. Optim. Methods Softw. 18 (2) (2003)
Satoru Fujishige, Zaifu Yang
A Note on Kelso and Crawford's Gross Substitutes Condition. Math. Oper. Res. 28 (3) (2003)
Akinobu Eguchi, Satoru Fujishige, Akihisa Tamura
A Generalized Gale-Shapley Algorithm for a Discrete-Concave Stable-Marriage Model. ISAAC (2003)
Hiro Ito, Kazuhisa Makino, Kouji Arata, Shoji Honami, Yuichiro Itatsu, Satoru Fujishige
Source location problem with flow requirements in directed networks. Optim. Methods Softw. 18 (4) (2003)
Satoru Fujishige
A maximum flow algorithm using MA ordering. Oper. Res. Lett. 31 (3) (2003)
Kouji Arata, Satoru Iwata, Kazuhisa Makino, Satoru Fujishige
Locating Sources to Meet Flow Demands in Undirected Networks. J. Algorithms 42 (1) (2002)
Satoko Mamada, Kazuhisa Makino, Satoru Fujishige
Optimal Sink Location Problem for Dynamic Flows in a Tree Network. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. (5) (2002)
Satoru Fujishige, Satoru Iwata
A descent method for submodular function minimization. Math. Program. 92 (2) (2002)
Kazuhisa Makino, Takashi Takabatake, Satoru Fujishige
A simple matching algorithm for regular bipartite graphs. Inf. Process. Lett. 84 (4) (2002)
Satoru Iwata, Lisa Fleischer, Satoru Fujishige
A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48 (4) (2001)
Satoru Fujishige, Sachin B. Patkar
Realization of set functions as cut functions of graphs and hypergraphs. Discret. Math. 226 (1-3) (2001)
Satoru Fujishige, Satoru Iwata
Bisubmodular Function Minimization. IPCO (2001)
Satoru Fujishige, Kazuo Murota
Notes on L-/M-convex functions and the separation theorems. Math. Program. 88 (1) (2000)
Kouji Arata, Satoru Iwata, Kazuhisa Makino, Satoru Fujishige
Locating Sources to Meet Flow Demands in Undirected Networks. SWAT (2000)
Satoru Fujishige
A note on Faigle and Kern's dual greedy polyhedra. Math. Program. 88 (1) (2000)
Satoru Fujishige
A laminarity property of the polyhedron described by a weakly posi-modular set function. Discret. Appl. Math. 100 (1-2) (2000)
Satoru Iwata, Lisa Fleischer, Satoru Fujishige
A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. STOC (2000)
Satoru Fujishige, Satoru Iwata
Minimizing a Submodular Function Arising From a Concave Function. Discret. Appl. Math. 92 (2-3) (1999)
Satoru Fujishige
A Min-Max Theorem for Bisubmodular Polyhedra. SIAM J. Discret. Math. 10 (2) (1997)
Kazutoshi Ando, Satoru Fujishige, Takeshi Naitoh
A characterization of bisubmodular functions. Discret. Math. 148 (1-3) (1996)
Kazutoshi Ando, Satoru Fujishige, Toshio Nemoto
Decomposition of a Bidirected Graph into Strongly Connected Components and Its Signed Poset Structure. Discret. Appl. Math. 68 (3) (1996)
Kazutoshi Ando, Satoru Fujishige
On structures of bisubmodular polyhedra. Math. Program. 74 (1996)
Kazuo Iwano, Shinji Misono, Shu Tezuka, Satoru Fujishige
A New Scaling Algorithm for the Maximum Mean Cut Problem. Algorithmica 11 (3) (1994)
Takeshi Naitoh, Satoru Fujishige
A note on the Frank-Tardos bi-truncation algorithm for crossing-submodular functions. Math. Program. 53 (1992)
Satoru Fujishige, Kazuo Iwano, J. Nakano, Shu Tezuka
A Speculative Contraction Method for Minimum Cost Flows: Toward a Practical Algorithm. Network Flows And Matching (1991)
Satoru Fujishige, Hans Röck, Uwe Zimmermann
A Strongly Polynomial Algorithm for Minimum Cost Submodular Flow Problems. Math. Oper. Res. 14 (1) (1989)
Satoru Fujishige
Optimization over the polyhedron determined by a submodular function on a co-intersecting family. Math. Program. 42 (1-3) (1988)
Satoru Fujishige, Naoki Katoh, Tetsuo Ichimori
The Fair Resource Allocation Problem with Submodular Constraints. Math. Oper. Res. 13 (1) (1988)
Satoru Fujishige
An out-of-kilter method for submodular flows. Discret. Appl. Math. 17 (1-2) (1987)
Kazuo Murota, Satoru Fujishige
Finding a homotopy base for directed paths in an acyclic graph. Discret. Appl. Math. 17 (1-2) (1987)
David F. Shanno, A. J. J. Talman, Satoru Fujishige, Steven Nahmias, Karl Straßner, Götz Uebe
Book reviews. Z. Oper. Research 30 (3) (1986)
Satoru Fujishige
A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm. Math. Program. 35 (3) (1986)
Satoru Fujishige
A decomposition of distributive lattices. Discret. Math. 55 (1) (1985)
Satoru Fujishige
Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions. Math. Program. 29 (2) (1984)
Satoru Fujishige
On the subdifferential of a submodular function. Math. Program. 29 (3) (1984)
Satoru Fujishige
Structures of polyhedra determined by submodular functions on crossing families. Math. Program. 29 (2) (1984)
Satoru Fujishige
A note on Frank's generalized polymatroids. Discret. Appl. Math. 7 (1) (1984)
Satoru Fujishige
Canonical decompositions of symmetric submodular systems. Discret. Appl. Math. 5 (2) (1983)
Satoru Fujishige
A note on the problem of updating shortest paths. Networks 11 (3) (1981)
Satoru Fujishige
An Efficient PQ-Graph Algorithm for Solving the Graph-Realization Problem. J. Comput. Syst. Sci. 21 (1) (1980)
Satoru Fujishige
Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector. Math. Oper. Res. 5 (2) (1980)
Satoru Fujishige
Canonical decompositions of symmetric submodular systems. Graph Theory and Algorithms (1980)
Satoru Fujishige
Principal structures of submodular systems. Discret. Appl. Math. 2 (1) (1980)
Satoru Fujishige
Polymatroidal Dependence Structure of a Set of Random Variables Inf. Control. 39 (1) (1978)
Satoru Fujishige
Comments on "Optimal Control of Unreliable Dynamic Systems with Discrete Time Inspections". IEEE Trans. Syst. Man Cybern. 6 (10) (1976)
Satoru Fujishige
Remarks on "optimal stochastic control for discrete-time linear system with interrupted observations". Autom. 10 (2) (1974)
Yoshikazu Sawaragi, T. Katayama, Satoru Fujishige
Sequential State Estimation with Interrupted Observation Inf. Control. 21 (1) (1972)