4 Search Results for "Prabhu, Milind"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.50
New Results on a General Class of Minimum Norm Optimization Problems

Authors: Kuowen Chen, Jian Li, Yuval Rabani, and Yiran Zhang

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the general norm optimization for combinatorial problems, initiated by Chakrabarty and Swamy (STOC 2019). We propose a general formulation that captures a large class of combinatorial structures: we are given a set 𝒰 of n weighted elements and a family of feasible subsets ℱ. Each subset S ∈ ℱ is called a feasible solution/set of the problem. We denote the value vector by v = {v_i}_{i ∈ [n]}, where v_i ≥ 0 is the value of element i. For any subset S ⊆ 𝒰, we use v[S] to denote the n-dimensional vector {v_e⋅ 𝟏[e ∈ S]}_{e ∈ 𝒰} (i.e., we zero out all entries that are not in S). Let f: ℝⁿ → ℝ_+ be a symmetric monotone norm function. Our goal is to minimize the norm objective f(v[S]) over feasible subset S ∈ ℱ. The problem significantly generalizes the corresponding min-sum and min-max problems. We present a general equivalent reduction of the norm minimization problem to a multi-criteria optimization problem with logarithmic budget constraints, up to a constant approximation factor. Leveraging this reduction, we obtain constant factor approximation algorithms for the norm minimization versions of several covering problems, such as interval cover, multi-dimensional knapsack cover, and logarithmic factor approximation for set cover. We also study the norm minimization versions for perfect matching, s-t path and s-t cut. We show the natural linear programming relaxations for these problems have a large integrality gap. To complement the negative result, we show that, for perfect matching, it is possible to obtain a bi-criteria result: for any constant ε,δ > 0, we can find in polynomial time a nearly perfect matching (i.e., a matching that matches at least 1-ε proportion of vertices) and its cost is at most (8+δ) times of the optimum for perfect matching. Moreover, we establish the existence of a polynomial-time O(log log n)-approximation algorithm for the norm minimization variant of the s-t path problem. Specifically, our algorithm achieves an α-approximation with a time complexity of n^{O(log log n / α)}, where 9 ≤ α ≤ log log n.
Cite as

Kuowen Chen, Jian Li, Yuval Rabani, and Yiran Zhang. New Results on a General Class of Minimum Norm Optimization Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2025.50,
  author =	{Chen, Kuowen and Li, Jian and Rabani, Yuval and Zhang, Yiran},
  title =	{{New Results on a General Class of Minimum Norm Optimization Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{50:1--50:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.50},
  URN =		{urn:nbn:de:0030-drops-234276},
  doi =		{10.4230/LIPIcs.ICALP.2025.50},
  annote =	{Keywords: Approximation Algorithms, Minimum Norm Optimization, Linear Programming}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2025.21
GSOHC: Global Synchronization Optimization in Heterogeneous Computing

Authors: Soumik Kumar Basu and Jyothi Vedurada

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract
The use of heterogeneous systems has become widespread and popular in the past decade with more than one type of processor, such as CPUs, GPUs (Graphics Processing Units), and FPGAs (Field Programmable Gate Arrays) etc. A wide range of applications use both CPU and GPU to leverage the benefits of their unique features and strengths. Therefore, collaborative computation between CPU and GPU is essential to achieve high program performance. However, poorly placed global synchronization barriers and synchronous memory transfers are the main bottlenecks to enhanced program performance, preventing CPU and GPU computations from overlapping. Based on this observation, we propose a new optimization technique called hetero-sync motion that can relocate such barrier instructions to new locations, resulting in improved performance in CPU-GPU heterogeneous programs. Further, we propose GSOHC, a compiler analysis and optimization framework that automatically finds opportunities for hetero-sync motion in the input program and then performs code transformation to apply the optimization. Our static analysis is a context-sensitive, flow-sensitive inter-procedural data-flow analysis with three phases to identify the optimization opportunities precisely. We have implemented GSOHC using LLVM/Clang infrastructure. On A4000, P100 and A100 GPUs, our optimization achieves speedups of up to 1.8x, 1.9x and 1.9x over the baseline, respectively.
Cite as

Soumik Kumar Basu and Jyothi Vedurada. GSOHC: Global Synchronization Optimization in Heterogeneous Computing. In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 21:1-21:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kumarbasu_et_al:LIPIcs.ECOOP.2025.21,
  author =	{Kumar Basu, Soumik and Vedurada, Jyothi},
  title =	{{GSOHC: Global Synchronization Optimization in Heterogeneous Computing}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{21:1--21:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.21},
  URN =		{urn:nbn:de:0030-drops-232949},
  doi =		{10.4230/LIPIcs.ECOOP.2025.21},
  annote =	{Keywords: Static Analysis, Synchronization, CPU-GPU, Heterogeneous Computing, Parallelization}
}
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}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 2 2023

  • Refine by Author
  • 2 Prabhu, Milind
  • 1 Assadi, Sepehr
  • 1 Ayyadevara, Nikhil
  • 1 Bansal, Nikhil
  • 1 Chen, Kuowen
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Linear programming
  • 1 Software and its engineering → Automated static analysis
  • 1 Software and its engineering → Compilers
  • Show More...

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 CPU-GPU
  • 1 Generalized Makespan
  • 1 Hardness of Approximation
  • 1 Heterogeneous Computing
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact