A simple combinatorial algorithm for submodular function minimization

A simple combinatorial algorithm for submodular function minimization

This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O(n6EO log nM) [O (n superscript 6 E O log nM)] time, where n is the cardinality of the ground set, M is the maximum absolute value of the function value, an...

Mô tả đầy đủ

Chi tiết về thư mục
Những tác giả chính:	Iwata, Satoru, Orlin, James B.
Tác giả khác:	Sloan School of Management
Định dạng:	Bài viết
Ngôn ngữ:	en_US
Được phát hành:	Society for Industrial and Applied Mathematics / Association for Computing Machinery 2011
Truy cập trực tuyến:	http://hdl.handle.net/1721.1/65187 https://orcid.org/0000-0002-7488-094X

Những quyển sách tương tự

Approximating Submodular Functions Everywhere
Bằng: Goemans, Michel X., et al.
Được phát hành: (2011)

Robust Monotone Submodular Function Maximization
Bằng: Orlin, James B, et al.
Được phát hành: (2021)

Robust monotone submodular function maximization
Bằng: Orlin, James B, et al.
Được phát hành: (2021)

Discrete Newton’s Algorithm for Parametric Submodular Function Minimization
Bằng: Goemans, Michel X, et al.
Được phát hành: (2018)

Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations
Bằng: Goemans, Michel X., et al.
Được phát hành: (2013)

A Combinatorial Approximation Algorithm for the Vector Scheduling with Submodular Penalties on Parallel Machines
Bằng: Bihui Cheng, et al.
Được phát hành: (2023-01-01)

Scheduling to Minimize Power Consumption using Submodular Functions
Bằng: Demaine, Erik D., et al.
Được phát hành: (2012)

Scheduling to minimize power consumption using submodular functions
Bằng: Zadimoghaddam, Morteza
Được phát hành: (2011)

Which submodular functions are expressible using binary submodular functions?
Bằng: Živný, S, et al.
Được phát hành: (2008)

Which submodular functions are expressible using binary submodular functions?
Bằng: Živný, S, et al.
Được phát hành: (2008)

Matchings, matroids and submodular functions
Bằng: Harvey, Nicholas James Alexander
Được phát hành: (2009)

Efficient minimization of higher order submodular functions using monotonic Boolean functions
Bằng: Ramalingam, S, et al.
Được phát hành: (2017)

Resilient monotone submodular function maximization
Bằng: Tzoumas, Vasileios, et al.
Được phát hành: (2018)

The Expressive Power of Binary Submodular Functions
Bằng: Zivny, S, et al.
Được phát hành: (2008)

The Expressive Power of Binary Submodular Functions.
Bằng: Zivny, S, et al.
Được phát hành: (2009)

Resilient monotone submodular function maximization
Bằng: Tzoumas, V, et al.
Được phát hành: (2017)

The Expressive Power of Binary Submodular Functions
Bằng: Živný, S, et al.
Được phát hành: (2009)

The Expressive Power of Binary Submodular Functions
Bằng: Živný, S, et al.
Được phát hành: (2008)

Maximizing k-submodular functions and beyond
Bằng: Ward, J, et al.
Được phát hành: (2016)

The Expressive Power of Binary Submodular Functions
Bằng: Zivny, S, et al.
Được phát hành: (2008)

The expressive power of binary submodular functions
Bằng: Živný, S, et al.
Được phát hành: (2009)

The expressive power of binary submodular functions
Bằng: ivný, S, et al.
Được phát hành: (2009)

The Expressive Power of Binary Submodular Functions
Bằng: Živný, S, et al.
Được phát hành: (2008)

The Expressive Power of Binary Submodular Functions
Bằng: Živný, S, et al.
Được phát hành: (2009)

The submodular joint replenishment problem
Bằng: Cheung, Maurice, et al.
Được phát hành: (2015)

Coxeter submodular functions and deformations of Coxeter permutahedra
Bằng: Ardila, Federico, et al.
Được phát hành: (2022)

Coxeter submodular functions and deformations of Coxeter permutahedra
Bằng: Ardila, Federico, et al.
Được phát hành: (2021)

A fast and simple algorithm for the maximum flow problem
Bằng: Ahuja, Ravindra K., et al.
Được phát hành: (2009)

A fast and simple algorithm for the maximum flow problem
Bằng: Ahuja, Ravindra K., et al.
Được phát hành: (2009)

Distributionally robust submodular maximization
Bằng: Staib, Matthew, et al.
Được phát hành: (2021)

Allowing non-submodular score functions in distributed task allocation
Bằng: Choi, Han-Lim, et al.
Được phát hành: (2013)

Approximate Local Search in Combinatorial Optimization
Bằng: Orlin, James B., et al.
Được phát hành: (2003)

Approximate Local Search in Combinatorial Optimization
Bằng: Orlin, James, et al.
Được phát hành: (2004)

On Maximizing Sums of Non-monotone Submodular and Linear Functions
Bằng: Qi, Benjamin
Được phát hành: (2023)

Robust Budget Allocation Via Continuous Submodular Functions
Bằng: Staib, Matthew, et al.
Được phát hành: (2021)

Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization
Bằng: Zhigang Li, et al.
Được phát hành: (2018-01-01)

Submodular Secretary Problem and Extensions
Bằng: Zadimoghaddam, Morteza, et al.
Được phát hành: (2010)

Exploiting submodular value functions for scaling up active perception
Bằng: Satsangi, Y, et al.
Được phát hành: (2017)

Attempting the Impossible: Enumerating Extremal Submodular Functions for n = 6
Bằng: Elod P. Csirmaz, et al.
Được phát hành: (2024-12-01)

Combinatorial algorithms for scheduling jobs to minimize server usage time
Bằng: Ren, Runtian
Được phát hành: (2018)