Posimodular function optimization

DOI10.1007/S00453-021-00910-YzbMath1491.68088OpenAlexW4210378701MaRDI QIDQ5918641

Magnús M. Halldórsson, Toshimasa Ishii, Kenjiro Takazawa, Kazuhisa Makino

Publication date: 22 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00910-y

zbMATH Keywords

algorithmlower boundsposimodular function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Parameterized complexity, tractability and kernelization (68Q27)

Uses Software

• EGRES

Cites Work

• Unnamed Item
• A note on minimizing submodular functions
• Minimum degree orderings
• Edge-connectivity augmentation problems
• Polyhedral structure of submodular and posi-modular systems
• Clustering with local restrictions
• A laminarity property of the polyhedron described by a weakly posi-modular set function
• Locating Sources to Meet Flow Demands in Undirected Networks
• Maximizing Non-monotone Submodular Functions
• POSI-MODULAR SYSTEMS WITH MODULOTONE REQUIREMENTS UNDER PERMUTATION CONSTRAINTS
• Minimum Transversals in Posimodular Systems
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(<Special Issue>Network Design, Control and Optimization)
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Approximation Algorithms for Submodular Multiway Partition
• Cutsets and partitions of hypergraphs
• Posimodular function optimization
• Augmenting a submodular and posi-modular set function by a multigraph

This page was built for publication: Posimodular function optimization