Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested

DOI10.1007/s13160-012-0085-xzbMath1254.90191OpenAlexW2001129746MaRDI QIDQ1926640

Satoru Fujishige

Publication date: 28 December 2012

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/167740

zbMATH Keywords

combinatorial optimizationdiscrete optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Research exposition (monographs, survey articles) pertaining to history and biography (01-02)

Related Items

A simple projection algorithm for linear programming problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on disjoint arborescences
• Graph connectivity and its augmentation: Applications of MA orderings
• Zonotopes and the LP-Newton method
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks
• Matroids on convex geometries (cg-matroids)
• Arc-disjoint in-trees in directed graphs
• A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph
• Submodular function minimization
• A general model for matroids and the greedy algorithm
• A faster strongly polynomial time algorithm for submodular function minimization
• A strongly polynomial minimum cost circulation algorithm
• On submodular function minimization
• An efficient PQ-graph algorithm for solving the graph-realization problem
• Minimization on submodular flows
• Submodular functions and optimization
• New algorithms for the intersection problem of submodular systems
• Discrete convex analysis
• Computational implementation of Fujishige's graph realizability algorithm
• Increasing the rooted connectivity of a digraph by one
• Minimizing a submodular function arising from a concave function
• Walrasian equilibrium with gross substitutes
• An algorithm for finding the minimum-norm point in the intersection of a convex polyhedron and a hyperplane
• A capacity scaling algorithm for convex cost submodular flows
• The MA-ordering max-flow algorithm is not strongly polynomial for directed networks
• An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set
• Notes on L-/M-convex functions and the separation theorems
• A maximum flow algorithm using MA ordering.
• On structures of bisubmodular polyhedra
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A characterization of bisubmodular functions
• Decomposition of a bidirected graph into strongly connected components and its signed poset structure
• Dual greedy polyhedra, choice functions, and abstract convex geometries
• Minimum cost source location problems with flow requirements
• A general two-sided matching market with discrete concave utility functions
• Cores of convex games
• Submodular functions and optimization.
• Locating Sources to Meet Flow Demands in Undirected Networks
• Theory of Principal Partitions Revisited
• Submodular function minimization and related topics
• A Structure Theory for the Parametric Submodular Intersection Problem
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• A DUAL ALGORITHM FOR FINDING THE MINIMUM-NORM POINT IN A POLYTOPE
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• A NOTE ON SUBMODULAR FUNCTIONS ON DISTRIBUTIVE LATTICES
• Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
• On the subdifferential of a submodular function
• Structures of polyhedra determined by submodular functions on crossing families
• Minimizing Continuous Extensions of Discrete Convex Functions with Linear Inequality Constraints
• Minimum Transversals in Posimodular Systems
• A Primal-Dual Algorithm for Submodular Flows
• The Partial Order of a Polymatroid Extreme Point
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• Submodular systems and related topics
• An Almost Linear-Time Algorithm for Graph Realization
• A Strongly Polynomial Algorithm for Minimum Cost Submodular Flow Problems
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• Converting Linear Programs to Network Problems
• A note on the problem of updating shortest paths
• Computing Maximal “Polymatroidal” Network Flows
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Optimal flows in networks with multiple sources and sinks
• A proof of the data compression theorem of Slepian and Wolf for ergodic sources (Corresp.)
• Matroid intersection algorithms
• Rado's theorem for polymatroids
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• Finding the nearest point in A polytope
• AN ALGORITHM FOR FINDING AN OPTIMAL INDEPENDENT LINKAGE
• A PRIMAL APPROACH TO THE INDEPENDENT ASSIGNMENT PROBLEM
• Nonnegative entropy measures of multivariate symmetric correlations
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• Polymatroidal dependence structure of a set of random variables
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
• A Min--Max Theorem for Bisubmodular Polyhedra
• THE MINIMUM-WEIGHT IDEAL PROBLEM FOR SIGNED POSETS
• A simple min-cut algorithm
• Discrete Convex Analysis
• NEW MAXIMUM FLOW ALGORITHMS BY MA ORDERMGS AND SCALING
• A Fast Parametric Maximum Flow Algorithm and Applications
• An Algorithm for Submodular Functions on Graphs
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER AN INTEGRAL BISUBMODULAR POLYHEDRON
• The Orthant Non-Interaction Theorem for Certain Combinatorial Polyhedra and its Implications in the Intersection and the Dilworth Truncation of Bisubmodular Functions
• Algorithms and Computation
• A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES
• A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis
• PRACTICAL EFFICIENCY OF MAXIMUM FLOW ALGORITHMS USING MA ORDERINGS AND PREFLOWS
• Bisubmodular Function Minimization
• Convex Analysis
• Noiseless coding of correlated information sources
• A Note on Kelso and Crawford's Gross Substitutes Condition