Fetching the paper…

Reading the bibliography…

2011

Symmetry and approximability of submodular maximization problems

Vondrak, Jan

Original
PDF
Post on X

Understand

A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem.

These results hold typically in the value oracle model, where the objective function is accessible via a black box returning f(S) for a given S.
We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of symmetry gap.
Our main result is that for any fixed instance that exhibits a certain symmetry gap in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries.

Symmetry and approximability of submodular maximization problems · Around

Built on

J. Edmonds
1970
Earlier work this paper cites.
J. Edmonds
1971
Earlier work this paper cites.
G. L. Nemhauser, L. A. Wolsey and M. L. Fisher
1978
Earlier work this paper cites.
M. L. Fisher, G. L. Nemhauser and L. A. Wolsey
1978
Earlier work this paper cites.
G. L. Nemhauser and L. A. Wolsey
1978
Earlier work this paper cites.
L. Wolsey
1982
Earlier work this paper cites.
L. Wolsey
1982
Earlier work this paper cites.
S. Fujishige
1983
Earlier work this paper cites.
L. Lovász
1983
Earlier work this paper cites.
A. Frank
1997
Earlier work this paper cites.
U. Feige
1998
Earlier work this paper cites.
A. Schrijver
2000
Earlier work this paper cites.

Similar

L. Fleischer, S. Fujishige and S. Iwata
2001
Cited alongside, same era.
A. Schrijver
2003
Cited alongside, same era.
A. Ageev and M. Sviridenko
2004
Cited alongside, same era.
M. Sviridenko
2004
Cited alongside, same era.
G. Calinescu, C. Chekuri, M. Pál and J. Vondrák
2007
Cited alongside, same era.
U. Feige, V. Mirrokni and J. Vondrák
2007
Cited alongside, same era.
N. Alon and J. Spencer
2008
Cited alongside, same era.
S. Khot, R. Lipton, E. Markakis and A. Mehta

Then

J. Lee, V. Mirrokni, V. Nagarajan and M. Sviridenko
2009
Later among the works it cites.
J. Lee, M. Sviridenko and J. Vondrák
2009
Later among the works it cites.
J. Vondrák
2009
Later among the works it cites.
J. Vondrák
2010
Later among the works it cites.
G. Calinescu, C. Chekuri, M. Pál and J. Vondrák
2011
Closest in time.
S. Dughmi, T. Roughgarden and Q. Yan
2011
Closest in time.
S. Dughmi and J. Vondrák
2011
Closest in time.
S. Oveis Gharan and J. Vondrák

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

2008

Cited alongside, same era.

V. Mirrokni, M. Schapira and J. Vondrák

2008

Cited alongside, same era.

J. Vondrák

2008

Cited alongside, same era.

A. Kulik, H. Shachnai and T. Tamir

2009

Cited alongside, same era.

2011

Closest in time.

N. Buchbinder, M. Feldman, J. Naor and R. Schwartz

2012

Closest in time.

S. Dobzinski and J. Vondrák

2012

Closest in time.

S. Dobzinski and J. Vondrák

2012

Closest in time.