Submodular Cost Allocation Problem and Applications

Cutsets and partitions of hypergraphs

Eugene L. Lawler · 1973

Earlier work this paper cites.

Submodular functions and convexity

László Lovász · 1983

Earlier work this paper cites.

The complexity of multiterminal cuts

Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis · 1992

Earlier work this paper cites.

Multiway cuts in node weighted graphs

Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis · 1994

Earlier work this paper cites.

Minimizing symmetric submodular functions

Maurice Queyranne · 1995

Earlier work this paper cites.

An improved approximation algorithm for multiway cut

Gruia Calinescu, Howard J. Karloff, and Yuval Rabani · 1998

Earlier work this paper cites.

Rounding algorithms for a geometric embedding of minimum multiway cut

David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, and Neal E. Young · 1999

Earlier work this paper cites.

Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields

Jon M. Kleinberg and Éva Tardos · 1999

Earlier work this paper cites.

A lower bound of 8/(7+(1/k)-1) on the integrality ratio of the calinescu-karloff-rabani relaxation for multiway cut

Ari Freund and Howard J. Karloff · 2000

Earlier work this paper cites.

Min-max multiway cut

Zoya Svitkina and Éva Tardos · 2004

Cited alongside, same era.

Greedy splitting algorithms for approximating multiway partition problems

Liang Zhao, Hiroshi Nagamochi, and Toshihide Ibaraki · 2005

Cited alongside, same era.

Facility location with hierarchical facility costs

Zoya Svitkina and Éva Tardos · 2006

Cited alongside, same era.

Maximizing a submodular set function subject to a matroid constraint (extended abstract)

Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák · 2007

Cited alongside, same era.

The Fixed-Hub Single Allocation Problem: A Geometric Rounding Approach

Dongdong Ge, Yinyu Ye, and Jiawei Zhang · 2007

Cited alongside, same era.

Submodular approximation: Sampling-based algorithms and lower bounds

Zoya Svitkina and Lisa Fleischer · 2008

Cited alongside, same era.

Approximability of combinatorial problems with multi-agent submodular cost functions

Gagan Goel, Chinmay Karande, Pushkar Tripathi, and Lei Wang · 2009

Later among the works it cites.

Approximating submodular functions everywhere

Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, and Vahab S. Mirrokni · 2009

Later among the works it cites.

Submodular function minimization under covering constraints

Satoru Iwata and Kiyohito Nagano · 2009

Later among the works it cites.

Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems

Kazumasa Okumoto, Takuro Fukunaga, and Hiroshi Nagamochi · 2009

Later among the works it cites.

Fast approximate energy minimization with label costs

Andrew Delong, Anton Osokin, Hossam N. Isack, and Yuri Boykov · 2010

Later among the works it cites.

Computing Minimum Multiway Cuts in Hypergraphs from Hypertree Packings

Takuro Fukunaga · 2010