blob: 2c5b67a7f44d978a4fb39ce9d63f1168515be5aa (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
Summary
=======
This papers studies submodular functions over a continuous domain: these
functions are sometimes referred to as "smooth" submodular functions and are
the direct generalization of discrete submodular functions for continuous
variables. While prior work has focused on obtaining algorithms and
optimization guarantees for minimizing smooth submodular functions, this paper
focuses on obtaining approximation guarantees for maximizing smooth submodular
functions. Specifically, the authors:
* give and prove a characterization of submodularity (and coordinate-wise
concavity) in terms of a diminishing return (DR) property. This is
a generalization of a well-known characterization in the discrete case.
* give a (1-1/e) approximation algorithm for smooth submodular functions which
are coordinate wise concave and monotone
* give a 1/3 approximation algorithm for arbitrary smooth submodular functions
* give examples of problems which lead to optimizing a smooth submodular
function
* validate their algorithms through experiments
Comments
========
Smooth submodular functions have gathered interest in the recent years and as
the authors point out, event though results were known for minimization, there
was a lack of results on the maximization side.
While it is interesting to see that the results of the discrete case translate
well to the continuous case, this is also the source of a (relative) weakness
of the paper: a lack of technical novelty.
Section 4 in particular is a direct adaptation of the continuous algorithm of
Vondrak 2008. I don't see any fundamental difference in the statement of the
algorithm and the proof follows a very similar technique. Also, it would have
been interesting to mention that the multilinear extension of a monotone
submodular function is DR-submodular to clearly show the connection with
already existing results.
The algorithm in section 5 is more novel: it draws heavily from the algorithm
of [Buchbinder 2012] but required an adaptation to the continuous case (and
a specific analysis).
It is interesting that the authors give examples where maximizing smooth
submodular functions arise. Some of these examples seem a bit contrived, but
I don't have enough domain-specific knowledge to judge this confidently.
The paper is well written overall, but suffers from some notations
inconsitencies locally which can be unsettling for the reader. Two examples:
* the definition of submodularity line 80 is given for arbitrary compact sets,
but later the authors seem to focs on the specific case of the positive orthant
of R^n, it is not clear if the results hold in the most general case.
* definition 3.1 is hard to read: is it necessary to introduce a ground set and
then the characteristic vectors of the ground set elements? why not simply use
R^n and the standard basis vectors?
|
