Hardness and approximation of submodular minimum linear ordering problems
The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost $$f(\cdot )$$...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2023
|
| Online Access: | https://hdl.handle.net/1721.1/153207 |
| _version_ | 1826206383655092224 |
|---|---|
| author | Farhadi, Majid Gupta, Swati Sun, Shengding Tetali, Prasad Wigal, Michael C. |
| author_facet | Farhadi, Majid Gupta, Swati Sun, Shengding Tetali, Prasad Wigal, Michael C. |
| author_sort | Farhadi, Majid |
| collection | MIT |
| description | The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost
$$f(\cdot )$$
f
(
·
)
due to an ordering
$$\sigma $$
σ
of the items (say [n]), i.e.,
$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$
min
σ
∑
i
∈
[
n
]
f
(
E
i
,
σ
)
, where
$$E_{i,\sigma }$$
E
i
,
σ
is the set of items mapped by
$$\sigma $$
σ
to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a
$$(2-\frac{1+\ell _{f}}{1+|E|})$$
(
2
-
1
+
ℓ
f
1
+
|
E
|
)
-approximation for monotone submodular MLOP where
$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$
ℓ
f
=
f
(
E
)
max
x
∈
E
f
(
{
x
}
)
satisfies
$$1 \le \ell _f \le |E|$$
1
≤
ℓ
f
≤
|
E
|
. Our theory provides new approximation bounds for special cases of the problem, in particular a
$$(2-\frac{1+r(E)}{1+|E|})$$
(
2
-
1
+
r
(
E
)
1
+
|
E
|
)
-approximation for the matroid MLOP, where
$$f = r$$
f
=
r
is the rank function of a matroid. We further show that minimum latency vertex cover is
$$\frac{4}{3}$$
4
3
-approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest. |
| first_indexed | 2024-09-23T13:28:19Z |
| format | Article |
| id | mit-1721.1/153207 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:28:19Z |
| publishDate | 2023 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1532072023-12-20T03:30:46Z Hardness and approximation of submodular minimum linear ordering problems Farhadi, Majid Gupta, Swati Sun, Shengding Tetali, Prasad Wigal, Michael C. The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost $$f(\cdot )$$ f ( · ) due to an ordering $$\sigma $$ σ of the items (say [n]), i.e., $$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ min σ ∑ i ∈ [ n ] f ( E i , σ ) , where $$E_{i,\sigma }$$ E i , σ is the set of items mapped by $$\sigma $$ σ to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a $$(2-\frac{1+\ell _{f}}{1+|E|})$$ ( 2 - 1 + ℓ f 1 + | E | ) -approximation for monotone submodular MLOP where $$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ ℓ f = f ( E ) max x ∈ E f ( { x } ) satisfies $$1 \le \ell _f \le |E|$$ 1 ≤ ℓ f ≤ | E | . Our theory provides new approximation bounds for special cases of the problem, in particular a $$(2-\frac{1+r(E)}{1+|E|})$$ ( 2 - 1 + r ( E ) 1 + | E | ) -approximation for the matroid MLOP, where $$f = r$$ f = r is the rank function of a matroid. We further show that minimum latency vertex cover is $$\frac{4}{3}$$ 4 3 -approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest. 2023-12-19T16:29:53Z 2023-12-19T16:29:53Z 2023-12-14 2023-12-17T04:09:43Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/153207 Farhadi, M., Gupta, S., Sun, S. et al. Hardness and approximation of submodular minimum linear ordering problems. Math. Program. (2023). PUBLISHER_CC en https://doi.org/10.1007/s10107-023-02038-z Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Farhadi, Majid Gupta, Swati Sun, Shengding Tetali, Prasad Wigal, Michael C. Hardness and approximation of submodular minimum linear ordering problems |
| title | Hardness and approximation of submodular minimum linear ordering problems |
| title_full | Hardness and approximation of submodular minimum linear ordering problems |
| title_fullStr | Hardness and approximation of submodular minimum linear ordering problems |
| title_full_unstemmed | Hardness and approximation of submodular minimum linear ordering problems |
| title_short | Hardness and approximation of submodular minimum linear ordering problems |
| title_sort | hardness and approximation of submodular minimum linear ordering problems |
| url | https://hdl.handle.net/1721.1/153207 |
| work_keys_str_mv | AT farhadimajid hardnessandapproximationofsubmodularminimumlinearorderingproblems AT guptaswati hardnessandapproximationofsubmodularminimumlinearorderingproblems AT sunshengding hardnessandapproximationofsubmodularminimumlinearorderingproblems AT tetaliprasad hardnessandapproximationofsubmodularminimumlinearorderingproblems AT wigalmichaelc hardnessandapproximationofsubmodularminimumlinearorderingproblems |