DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.21

On Minimizing Generalized Makespan on Unrelated Machines

Authors: Nikhil Ayyadevara, Nikhil Bansal, and Milind Prabhu

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract

We consider the Generalized Makespan Problem (GMP) on unrelated machines, where we are given n jobs and m machines and each job j has arbitrary processing time p_{ij} on machine i. Additionally, there is a general symmetric monotone norm ψ_i for each machine i, that determines the load on machine i as a function of the sizes of jobs assigned to it. The goal is to assign the jobs to minimize the maximum machine load. Recently, Deng, Li, and Rabani [Deng et al., 2023] gave a 3 approximation for GMP when the ψ_i are top-k norms, and they ask the question whether an O(1) approximation exists for general norms ψ? We answer this negatively and show that, under natural complexity assumptions, there is some fixed constant δ > 0, such that GMP is Ω(log^δ n) hard to approximate. We also give an Ω(log^{1/2} n) integrality gap for the natural configuration LP.

Cite as

Nikhil Ayyadevara, Nikhil Bansal, and Milind Prabhu. On Minimizing Generalized Makespan on Unrelated Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ayyadevara_et_al:LIPIcs.APPROX/RANDOM.2023.21,
  author =	{Ayyadevara, Nikhil and Bansal, Nikhil and Prabhu, Milind},
  title =	{{On Minimizing Generalized Makespan on Unrelated Machines}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.21},
  URN =		{urn:nbn:de:0030-drops-188462},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.21},
  annote =	{Keywords: Hardness of Approximation, Generalized Makespan}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2023.19

Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs

Authors: Sepehr Assadi, Nirmit Joshi, Milind Prabhu, and Vihan Shah

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract

Estimating quantiles, like the median or percentiles, is a fundamental task in data mining and data science. A (streaming) quantile summary is a data structure that can process a set S of n elements in a streaming fashion and at the end, for any ϕ ∈ (0,1], return a ϕ-quantile of S up to an ε error, i.e., return a ϕ'-quantile with ϕ' = ϕ ± ε. We are particularly interested in comparison-based summaries that only compare elements of the universe under a total ordering and are otherwise completely oblivious of the universe. The best known deterministic quantile summary is the 20-year old Greenwald-Khanna (GK) summary that uses O((1/ε) log{(ε n)}) space [SIGMOD'01]. This bound was recently proved to be optimal for all deterministic comparison-based summaries by Cormode and Vesleý [PODS'20]. In this paper, we study weighted quantiles, a generalization of the quantiles problem, where each element arrives with a positive integer weight which denotes the number of copies of that element being inserted. The only known method of handling weighted inputs via GK summaries is the naive approach of breaking each weighted element into multiple unweighted items, and feeding them one by one to the summary, which results in a prohibitively large update time (proportional to the maximum weight of input elements). We give the first non-trivial extension of GK summaries for weighted inputs and show that it takes O((1/ε) log(εn)) space and O(log(1/ε)+log log(εn)) update time per element to process a stream of length n (under some quite mild assumptions on the range of weights and ε). En route to this, we also simplify the original GK summaries for unweighted quantiles.

Cite as

Sepehr Assadi, Nirmit Joshi, Milind Prabhu, and Vihan Shah. Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ICDT.2023.19,
  author =	{Assadi, Sepehr and Joshi, Nirmit and Prabhu, Milind and Shah, Vihan},
  title =	{{Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.19},
  URN =		{urn:nbn:de:0030-drops-177618},
  doi =		{10.4230/LIPIcs.ICDT.2023.19},
  annote =	{Keywords: Streaming algorithms, Quantile summaries, Rank estimation}
}

Search Results

Documents authored by Prabhu, Milind

On Minimizing Generalized Makespan on Unrelated Machines

Abstract

Cite as

Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs

Abstract

Cite as

Thanks for your feedback!

Could not send message