دورية أكاديمية
Hardness and approximation of submodular minimum linear ordering problems
| العنوان: | Hardness and approximation of submodular minimum linear ordering problems |
|---|---|
| المؤلفون: | Farhadi, Majid, Gupta, Swati, Sun, Shengding, Tetali, Prasad, Wigal, Michael C. |
| المصدر: | Springer Berlin Heidelberg |
| بيانات النشر: | Springer Berlin Heidelberg |
| سنة النشر: | 2023 |
| المجموعة: | DSpace@MIT (Massachusetts Institute of Technology) |
| الوصف: | 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. |
| نوع الوثيقة: | article in journal/newspaper |
| وصف الملف: | application/pdf |
| اللغة: | English |
| العلاقة: | https://doi.org/10.1007/s10107-023-02038-zTest; https://hdl.handle.net/1721.1/153207Test; Farhadi, M., Gupta, S., Sun, S. et al. Hardness and approximation of submodular minimum linear ordering problems. Math. Program. (2023).; PUBLISHER_CC |
| الإتاحة: | https://doi.org/10.1007/s10107-023-02038-zTest https://hdl.handle.net/1721.1/153207Test |
| حقوق: | Creative Commons Attribution ; https://creativecommons.org/licenses/by/4.0Test/ ; The Author(s) |
| رقم الانضمام: | edsbas.355FFCDC |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |