5 Search Results for "Kulkarni, Janardhan"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.109
The Greedy Algorithm Is not Optimal for On-Line Edge Coloring

Authors: Amin Saberi and David Wajc

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no online edge-coloring algorithm can edge color a graph optimally. Indeed, their work, titled "the greedy algorithm is optimal for on-line edge coloring", shows that the competitive ratio of 2 of the naïve greedy algorithm is best possible online. However, their lower bound required bounded-degree graphs, of maximum degree Δ = O(log n), which prompted them to conjecture that better bounds are possible for higher-degree graphs. While progress has been made towards resolving this conjecture for restricted inputs and arrivals or for random arrival orders, an answer for fully general adversarial arrivals remained elusive. We resolve this thirty-year-old conjecture in the affirmative, presenting a (1.9+o(1))-competitive online edge coloring algorithm for general graphs of degree Δ = ω(log n) under vertex arrivals. At the core of our results, and of possible independent interest, is a new online algorithm which rounds a fractional bipartite matching x online under vertex arrivals, guaranteeing that each edge e is matched with probability (1/2+c)⋅ x_e, for a constant c > 0.027.
Cite as

Amin Saberi and David Wajc. The Greedy Algorithm Is not Optimal for On-Line Edge Coloring. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 109:1-109:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{saberi_et_al:LIPIcs.ICALP.2021.109,
  author =	{Saberi, Amin and Wajc, David},
  title =	{{The Greedy Algorithm Is not Optimal for On-Line Edge Coloring}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{109:1--109:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.109},
  URN =		{urn:nbn:de:0030-drops-141786},
  doi =		{10.4230/LIPIcs.ICALP.2021.109},
  annote =	{Keywords: Online algorithms, edge coloring, greedy, online matching}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.42
On the Facility Location Problem in Online and Dynamic Models

Authors: Xiangyu Guo, Janardhan Kulkarni, Shi Li, and Jiayi Xian

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

Abstract
In this paper we study the facility location problem in the online with recourse and dynamic algorithm models. In the online with recourse model, clients arrive one by one and our algorithm needs to maintain good solutions at all time steps with only a few changes to the previously made decisions (called recourse). We show that the classic local search technique can lead to a (1+√2+ε)-competitive online algorithm for facility location with only O(log n/ε log 1/ε) amortized facility and client recourse, where n is the total number of clients arrived during the process. We then turn to the dynamic algorithm model for the problem, where the main goal is to design fast algorithms that maintain good solutions at all time steps. We show that the result for online facility location, combined with the randomized local search technique of Charikar and Guha [Charikar and Guha, 2005], leads to a (1+√2+ε)-approximation dynamic algorithm with total update time of Õ(n²) in the incremental setting against adaptive adversaries. The approximation factor of our algorithm matches the best offline analysis of the classic local search algorithm. Finally, we study the fully dynamic model for facility location, where clients can both arrive and depart. Our main result is an O(1)-approximation algorithm in this model with O(|F|) preprocessing time and O(nlog³ D) total update time for the HST metric spaces, where |F| is the number of potential facility locations. Using the seminal results of Bartal [Bartal, 1996] and Fakcharoenphol, Rao and Talwar [Fakcharoenphol et al., 2003], which show that any arbitrary N-point metric space can be embedded into a distribution over HSTs such that the expected distortion is at most O(log N), we obtain an O(log |F|) approximation with preprocessing time of O(|F|²log |F|) and O(nlog³ D) total update time. The approximation guarantee holds in expectation for every time step of the algorithm, and the result holds in the oblivious adversary model.
Cite as

Xiangyu Guo, Janardhan Kulkarni, Shi Li, and Jiayi Xian. On the Facility Location Problem in Online and Dynamic Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 42:1-42:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.APPROX/RANDOM.2020.42,
  author =	{Guo, Xiangyu and Kulkarni, Janardhan and Li, Shi and Xian, Jiayi},
  title =	{{On the Facility Location Problem in Online and Dynamic Models}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{42:1--42:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.42},
  URN =		{urn:nbn:de:0030-drops-126452},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.42},
  annote =	{Keywords: Facility location, online algorithm, recourse}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.16
Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models

Authors: Janardhan Kulkarni and Shi Li

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

Abstract
Scheduling a set of jobs over a collection of machines is a fundamental problem that needs to be solved millions of times a day in various computing platforms: in operating systems, in large data clusters, and in data centers. Along with makespan, flow-time, which measures the length of time a job spends in a system before it completes, is arguably the most important metric to measure the performance of a scheduling algorithm. In recent years, there has been a remarkable progress in understanding flow-time based objective functions in diverse settings such as unrelated machines scheduling, broadcast scheduling, multi-dimensional scheduling, to name a few. Yet, our understanding of the flow-time objective is limited mostly to the scenarios where jobs have no dependencies. On the other hand, in almost all real world applications, think of MapReduce settings for example, jobs have dependencies that need to be respected while making scheduling decisions. In this paper, we take first steps towards understanding this complex problem. In particular, we consider two classical scheduling problems that capture dependencies across jobs: 1) concurrent open-shop scheduling (COSSP) and 2) precedence constrained scheduling. Our main motivation to study these problems specifically comes from their relevance to two scheduling problems that have gained importance in the context of data centers: co-flow scheduling and DAG scheduling. We design almost optimal approximation algorithms for COSSP and PCSP, and show hardness results.
Cite as

Janardhan Kulkarni and Shi Li. Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kulkarni_et_al:LIPIcs.APPROX-RANDOM.2018.16,
  author =	{Kulkarni, Janardhan and Li, Shi},
  title =	{{Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{16:1--16:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.16},
  URN =		{urn:nbn:de:0030-drops-94205},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.16},
  annote =	{Keywords: Approximation, Weighted Flow Time, Concurrent Open Shop, Precedence Constraints}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.10
A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints

Authors: Sungjin Im, Janardhan Kulkarni, Benjamin Moseley, and Kamesh Munagala

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

Abstract
Modern data centers consist of a large number of heterogeneous resources such as CPU, memory, network bandwidth, etc. The resources are pooled into clusters for various reasons such as scalability, resource consolidation, and privacy. Clusters are often heterogeneous so that they can better serve jobs with different characteristics submitted from clients. Each job benefits differently depending on how much resource is allocated to the job, which in turn translates to how quickly the job gets completed. In this paper, we formulate this setting, which we term Multi-Cluster Polytope Scheduling (MCPS). In MCPS, a set of n jobs arrive over time to be executed on m clusters. Each cluster i is associated with a polytope P_i, which constrains how fast one can process jobs assigned to the cluster. For MCPS, we seek to optimize the popular objective of minimizing average weighted flow time of jobs in the online setting. We give a constant competitive algorithm with small constant resource augmentation for a large class of polytopes, which capture many interesting problems that arise in practice. Further, our algorithm is non-clairvoyant. Our algorithm and analysis combine and generalize techniques developed in the recent results for the classical unrelated machines scheduling and the polytope scheduling problem [10,12,11].
Cite as

Sungjin Im, Janardhan Kulkarni, Benjamin Moseley, and Kamesh Munagala. A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{im_et_al:LIPIcs.APPROX-RANDOM.2016.10,
  author =	{Im, Sungjin and Kulkarni, Janardhan and Moseley, Benjamin and Munagala, Kamesh},
  title =	{{A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.10},
  URN =		{urn:nbn:de:0030-drops-66336},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.10},
  annote =	{Keywords: Polytope constraints, average flow time, multi-clusters, online scheduling, and competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.143
Competitive Analysis of Constrained Queueing Systems

Authors: Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We consider the classical problem of constrained queueing (or switched networks): There is a set of N queues to which unit sized packets arrive. The queues are interdependent, so that at any time step, only a subset of the queues can be activated. One packet from each activated queue can be transmitted, and leaves the system. The set of feasible subsets that can be activated, denoted S, is downward closed and is known in advance. The goal is to find a scheduling policy that minimizes average delay (or flow time) of the packets. The constrained queueing problem models several practical settings including packet transmission in wireless networks and scheduling cross-bar switches. In this paper, we study this problem using the the competitive analysis: The packet arrivals can be adversarial and the scheduling policy only uses information about packets currently queued in the system. We present an online algorithm, that for any epsilon > 0, has average flow time at most O(R^2/epsilon^3*OPT+NR) when given (1+epsilon) speed, i.e., the ability to schedule (1+epsilon) packets on average per time step. Here, R is the maximum number of queues that can be simultaneously scheduled, and OPT is the average flow time of the optimal policy. This asymptotic competitive ratio O(R^3/epsilon^3) improves upon the previous O(N/epsilon^2) which was obtained in the context of multi-dimensional scheduling [Im/Kulkarni/Munagala, FOCS 2015]. In the full general model where N can be exponentially larger than R, this is an exponential improvement. The algorithm presented in this paper is based on Makespan estimates which is very different from that in [Im/Kulkarni/Munagala, FOCS 2015], a variation of the Max-Weight algorithm. Further, our policy is myopic, meaning that scheduling decisions at any step are based only on the current composition of the queues. We finally show that speed augmentation is necessary to achieve any bounded competitive ratio.
Cite as

Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive Analysis of Constrained Queueing Systems. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 143:1-143:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{im_et_al:LIPIcs.ICALP.2016.143,
  author =	{Im, Sungjin and Kulkarni, Janardhan and Munagala, Kamesh},
  title =	{{Competitive Analysis of Constrained Queueing Systems}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{143:1--143:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.143},
  URN =		{urn:nbn:de:0030-drops-62876},
  doi =		{10.4230/LIPIcs.ICALP.2016.143},
  annote =	{Keywords: Online scheduling, Average flow time, Switch network, Adversarial}
}
  • Refine by Author
  • 4 Kulkarni, Janardhan
  • 2 Im, Sungjin
  • 2 Li, Shi
  • 2 Munagala, Kamesh
  • 1 Guo, Xiangyu
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Online algorithms
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → Scheduling algorithms

  • Refine by Keyword
  • 1 Adversarial
  • 1 Approximation
  • 1 Average flow time
  • 1 Concurrent Open Shop
  • 1 Facility location
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2016
  • 1 2018
  • 1 2020
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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