Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917136037838848 |
|---|---|
| author | Harris, David G. |
| author_facet | Harris, David G. |
| contents | We describe a new dependent-rounding algorithmic framework for bipartite graphs. Given a fractional assignment $\vec x$ of values to edges of graph $G = (U \cup V, E)$, the algorithms return an integral solution $\vec X$ such that each right-node $v \in V$ has at most one neighboring edge $f$ with $X_f = 1$, and the variables $X_e$ also satisfy broad nonpositive-correlation properties. In particular, for any edges $e_1, e_2$ sharing a left-node $u \in U$, the variables $X_{e_1}, X_{e_2}$ have strong negative correlation, i.e. the expectation of $X_{e_1} X_{e_2}$ is significantly below $x_{e_1} x_{e_2}$.
This algorithm is based on generating negatively-correlated Exponential random variables and using them in a contention-resolution scheme inspired by an algorithm Im & Shadloo (2020). Our algorithm gives stronger and much more flexible negative correlation properties.
Dependent rounding schemes with negative correlation properties have been used for approximation algorithms for job-scheduling on unrelated machines to minimize weighted completion times (Bansal, Srinivasan, & Svensson (2021), Im & Shadloo (2020), Im & Li (2023)). Using our new dependent-rounding algorithm, among other improvements, we obtain a $1.398$-approximation for this problem. This significantly improves over the prior $1.45$-approximation ratio of Im & Li (2023). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_07476 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time Harris, David G. Data Structures and Algorithms We describe a new dependent-rounding algorithmic framework for bipartite graphs. Given a fractional assignment $\vec x$ of values to edges of graph $G = (U \cup V, E)$, the algorithms return an integral solution $\vec X$ such that each right-node $v \in V$ has at most one neighboring edge $f$ with $X_f = 1$, and the variables $X_e$ also satisfy broad nonpositive-correlation properties. In particular, for any edges $e_1, e_2$ sharing a left-node $u \in U$, the variables $X_{e_1}, X_{e_2}$ have strong negative correlation, i.e. the expectation of $X_{e_1} X_{e_2}$ is significantly below $x_{e_1} x_{e_2}$. This algorithm is based on generating negatively-correlated Exponential random variables and using them in a contention-resolution scheme inspired by an algorithm Im & Shadloo (2020). Our algorithm gives stronger and much more flexible negative correlation properties. Dependent rounding schemes with negative correlation properties have been used for approximation algorithms for job-scheduling on unrelated machines to minimize weighted completion times (Bansal, Srinivasan, & Svensson (2021), Im & Shadloo (2020), Im & Li (2023)). Using our new dependent-rounding algorithm, among other improvements, we obtain a $1.398$-approximation for this problem. This significantly improves over the prior $1.45$-approximation ratio of Im & Li (2023). |
| title | Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2308.07476 |