A faster strongly polynomial time algorithm for submodular function minimization (Q1016120): Difference between revisions

For the problem of minimizing a submodular function \(f(x)\) on a finite set \(V\) a strongly polynomial oracle algorithm is suggested. The algorithm uses distance functions and exploits optimality conditions.

0 references

reviewed by

Stephan Dempe

0 references

zbMATH Keywords

submodular function minimization

0 references

strongly polynomial time algorithm

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/s10107-007-0189-2

0 references

cites work

Q4326384

0 references

Q2747613

0 references

On submodular function minimization

0 references

Improved algorithms for submodular function minimization and submodular flow

0 references

Submodular functions and optimization.

0 references

Geometric algorithms and combinatorial optimization

0 references

A Faster Scaling Algorithm for Minimizing Submodular Functions

0 references

Submodular function minimization

0 references

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

0 references

Q5292089

0 references

A combinatorial algorithm minimizing submodular functions in strongly polynomial time.

0 references

Combinatorial optimization. Polyhedra and efficiency (3 volumes)

0 references

Cores of convex games

0 references

A note on Schrijver's submodular function minimization algorithm.

0 references

Identifiers

zbMATH Open document ID

1179.90290

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

10.1007/S10107-007-0189-2

0 references

DBLP publication ID

journals/mp/Orlin09

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1016120

@@ Property / DOI @@
-.1007/s10107-007-0189-2
@@ Property / DOI: 10.1007/s10107-007-0189-2 / rank @@
-Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s10107-007-0189-2
+Normal rank
@@ Property / OpenAlex ID @@
+W2050511894
@@ Property / OpenAlex ID: W2050511894 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4326384
@@ Property / cites work: Q4326384 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2747613
@@ Property / cites work: Q2747613 / rank @@
+Normal rank
@@ Property / cites work @@
+On submodular function minimization
@@ Property / cites work: On submodular function minimization / rank @@
+Normal rank
@@ Property / cites work @@
+Improved algorithms for submodular function minimization and submodular flow
+Normal rank
@@ Property / cites work @@
+Submodular functions and optimization.
@@ Property / cites work: Submodular functions and optimization. / rank @@
+Normal rank
@@ Property / cites work @@
+Geometric algorithms and combinatorial optimization
+Normal rank
@@ Property / cites work @@
+A Faster Scaling Algorithm for Minimizing Submodular Functions
+Normal rank
@@ Property / cites work @@
+Submodular function minimization
@@ Property / cites work: Submodular function minimization / rank @@
+Normal rank
@@ Property / cites work @@
+A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
+Normal rank
@@ Property / cites work @@
+Q5292089
@@ Property / cites work: Q5292089 / rank @@
+Normal rank
@@ Property / cites work @@
+A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
+Normal rank
@@ Property / cites work @@
+Combinatorial optimization. Polyhedra and efficiency (3 volumes)
+Normal rank
@@ Property / cites work @@
+Cores of convex games
@@ Property / cites work: Cores of convex games / rank @@
+Normal rank
@@ Property / cites work @@
+A note on Schrijver's submodular function minimization algorithm.
+Normal rank
@@ Property / Wikidata QID @@
+Q59592328
@@ Property / Wikidata QID: Q59592328 / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/S10107-007-0189-2
@@ Property / DOI: 10.1007/S10107-007-0189-2 / rank @@
+Normal rank
@@ Property / DBLP publication ID @@
+journals/mp/Orlin09
@@ Property / DBLP publication ID: journals/mp/Orlin09 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1016120