Search

Your search keyword '"Srivastav, Abhinav"' showing total 27 results
Start Over Author "Srivastav, Abhinav"

Refine your results

more »

more »

more »
27 results on '"Srivastav, Abhinav"'

2. Online Non-Monotone DR-submodular Maximization

Author

Thang, Nguyen Kim and Srivastav, Abhinav

Subjects
Computer Science - Machine Learning, Computer Science - Data Structures and Algorithms, Statistics - Machine Learning
Abstract

In this paper, we study fundamental problems of maximizing DR-submodular continuous functions that have real-world applications in the domain of machine learning, economics, operations research and communication systems. It captures a subclass of non-convex optimization that provides both theoretical and practical guarantees. Here, we focus on minimizing regret for online arriving non-monotone DR-submodular functions over different types of convex sets: hypercube, down-closed and general convex sets. First, we present an online algorithm that achieves a $1/e$-approximation ratio with the regret of $O(T^{2/3})$ for maximizing DR-submodular functions over any down-closed convex set. Note that, the approximation ratio of $1/e$ matches the best-known guarantee for the offline version of the problem. Moreover, when the convex set is the hypercube, we propose a tight 1/2-approximation algorithm with regret bound of $O(\sqrt{T})$. Next, we give an online algorithm that achieves an approximation guarantee (depending on the search space) for the problem of maximizing non-monotone continuous DR-submodular functions over a \emph{general} convex set (not necessarily down-closed). To best of our knowledge, no prior algorithm with approximation guarantee was known for non-monotone DR-submodular maximization in the online setting. Finally we run experiments to verify the performance of our algorithms on problems arising in machine learning domain with the real-world datasets.

Published
2019

4. Non-monotone DR-submodular Maximization: Approximation and Regret Guarantees

Author

Dürr, Christoph, Thang, Nguyen Kim, Srivastav, Abhinav, and Tible, Léo

Subjects
Computer Science - Machine Learning, Computer Science - Data Structures and Algorithms, Mathematics - Optimization and Control, Statistics - Machine Learning
Abstract

Diminishing-returns (DR) submodular optimization is an important field with many real-world applications in machine learning, economics and communication systems. It captures a subclass of non-convex optimization that provides both practical and theoretical guarantees. In this paper, we study the fundamental problem of maximizing non-monotone DR-submodular functions over down-closed and general convex sets in both offline and online settings. First, we show that for offline maximizing non-monotone DR-submodular functions over a general convex set, the Frank-Wolfe algorithm achieves an approximation guarantee which depends on the convex set. Next, we show that the Stochastic Gradient Ascent algorithm achieves a 1/4-approximation ratio with the regret of $O(1/\sqrt{T})$ for the problem of maximizing non-monotone DR-submodular functions over down-closed convex sets. These are the first approximation guarantees in the corresponding settings. Finally we benchmark these algorithms on problems arising in machine learning domain with the real-world datasets.

Published
2019

5. Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines

Author

Lucarelli, Giorgio, Moseley, Benjamin, Thang, Nguyen Kim, Srivastav, Abhinav, and Trystram, Denis

Subjects
Computer Science - Data Structures and Algorithms
Abstract

In this paper, we consider the online problem of scheduling independent jobs \emph{non-preemptively} so as to minimize the weighted flow-time on a set of unrelated machines. There has been a considerable amount of work on this problem in the preemptive setting where several competitive algorithms are known in the classical competitive model. %Using the speed augmentation model, Anand et al. showed that the greedy algorithm is $O\left(\frac{1}{\epsilon}\right)$-competitive in the preemptive setting. In the non-preemptive setting, Lucarelli et al. showed that there exists a strong lower bound for minimizing weighted flow-time even on a single machine. However, the problem in the non-preemptive setting admits a strong lower bound. Recently, Lucarelli et al. presented an algorithm that achieves a $O\left(\frac{1}{\epsilon^2}\right)$-competitive ratio when the algorithm is allowed to reject $\epsilon$-fraction of total weight of jobs and $\epsilon$-speed augmentation. They further showed that speed augmentation alone is insufficient to derive any competitive algorithm. An intriguing open question is whether there exists a scalable competitive algorithm that rejects a small fraction of total weights. In this paper, we affirmatively answer this question. Specifically, we show that there exists a $O\left(\frac{1}{\epsilon^3}\right)$-competitive algorithm for minimizing weighted flow-time on a set of unrelated machine that rejects at most $O(\epsilon)$-fraction of total weight of jobs. The design and analysis of the algorithm is based on the primal-dual technique. Our result asserts that alternative models beyond speed augmentation should be explored when designing online schedulers in the non-preemptive setting in an effort to find provably good algorithms.

Published
2018

6. Online Non-preemptive Scheduling on Unrelated Machines with Rejections

Author

Lucarelli, Giorgio, Moseley, Benjamin, Thang, Nguyen Kim, Srivastav, Abhinav, and Trystram, Denis

Subjects
Computer Science - Data Structures and Algorithms
Abstract

When a computer system schedules jobs there is typically a significant cost associated with preempting a job during execution. This cost can be from the expensive task of saving the memory's state and loading data into and out of memory. It is desirable to schedule jobs non-preemptively to avoid the costs of preemption. There is a need for non-preemptive system schedulers on desktops, servers and data centers. Despite this need, there is a gap between theory and practice. Indeed, few non-preemptive \emph{online} schedulers are known to have strong foundational guarantees. This gap is likely due to strong lower bounds on any online algorithm for popular objectives. Indeed, typical worst case analysis approaches, and even resource augmented approaches such as speed augmentation, result in all algorithms having poor performance guarantees. This paper considers on-line non-preemptive scheduling problems in the worst-case rejection model where the algorithm is allowed to reject a small fraction of jobs. By rejecting only a few jobs, this paper shows that the strong lower bounds can be circumvented. This approach can be used to discover algorithmic scheduling policies with desirable worst-case guarantees. Specifically, the paper presents algorithms for the following two objectives: minimizing the total flow-time and minimizing the total weighted flow-time plus energy under the speed-scaling mechanism. The algorithms have a small constant competitive ratio while rejecting only a constant fraction of jobs. Beyond specific results, the paper asserts that alternative models beyond speed augmentation should be explored to aid in the discovery of good schedulers in the face of the requirement of being online and non-preemptive.

Published
2018

8. Multi-Centric Validation of Truenat MTB Rif Dx for Diagnosis of Extrapulmonary Tuberculosis

Author

B. Singh, Urvashi, primary, Singh, Manjula, additional, Rodrigues, Camilla, additional, Christopher, Devasahayam Jesus, additional, Mahajan, Neeraj, additional, Srivastav, Abhinav, additional, Singh, Jitenkumar, additional, Kanswal, Sunita, additional, Rao, M. Vishnu Vardhana, additional, Kazi, Mubin, additional, Sawant, Damini, additional, Thangakunam, Balamugesh, additional, Vijay, Coelho Victor, additional, Shankar, Deepa, additional, Bhatnagar, Anuj, additional, Mohan, Anant, additional, and Ahuja, Vineet, additional

Published
2024
Full Text
View/download PDF

9. Total stretch minimization on single and identical parallel machines

Author

Srivastav, Abhinav and Trystram, Denis

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We consider the classical problem of scheduling $n$ jobs with release dates on both single and identical parallel machines. We measure the quality of service provided to each job by its stretch, which is defined as the ratio of its response time to processing time. Our objective is to schedule these jobs non-preemptively so as to minimize sum stretch. So far, there have been very few results for sum stretch minimization especially for the non-preemptive case. For the preemptive version, the Shortest remaining processing time (SRPT) algorithm is known to give $2$-competitive for sum stretch on single machine while its is $13$-competitive on identical parallel machines. Leonardi and Kellerer provided the strong lower bound for the more general problem of \textit{sum (weighted) flow time} in single machine and identical parallel machines, respectively . Therefore, we study this problem with some additional assumptions and present two new competitive ratio for existing algorithms. We show that the Shortest processing time (SPT) algorithm is $\Delta - \frac{1}{\Delta}+1$-competitive for non-preemptive sum stretch minimization on single machine and it is $\Delta - \frac{1}{\Delta}+ \frac{3}{2} -\frac{1}{2m}$ on $m$ identical parallel machines, where $\Delta$ is the upper bound on the ratio between the maximum and the minimum processing time of the jobs., Comment: Submitted to ISAAC, 2014

Published
2014

10. From Preemptive to Non-preemptive Scheduling Using Rejections

Author

Lucarelli, Giorgio, Srivastav, Abhinav, Trystram, Denis, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Dinh, Thang N., editor, and Thai, My T., editor

Published
2016
Full Text
View/download PDF

11. Online Non-preemptive Scheduling to Optimize Max Stretch on a Single Machine

Author

Dutot, Pierre-Francois, Saule, Erik, Srivastav, Abhinav, Trystram, Denis, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Dinh, Thang N., editor, and Thai, My T., editor

Published
2016
Full Text
View/download PDF

12. Persistent SARS-CoV-2 infections in Immunocompromised hosts contribute to new variants

Author

Singh, Urvashi B, primary, Imran, Mohamed, additional, Chaudhry, Rama, additional, Jolly, Bani, additional, Bala, Kiran, additional, Senthivel, Vigneshwar, additional, Srivastav, Abhinav, additional, Rophina, Mercy, additional, Bir, Raunak, additional, Bhoyar, Rahul C., additional, Kumari, Lata, additional, V.R., Arvinden, additional, Jamshed, Nayer, additional, divakar, Mohit kumar, additional, Aggarwal, Praveen, additional, Shamnath, Afra, additional, Sinha, Subrata, additional, Gupta, Vishu, additional, Bajaj, Anjali, additional, GROUP, COVID CBNAAT CORE, additional, Sivasubbu, Sridhar, additional, Scaria, Vinod, additional, and Guleria, Randeep, additional

Published
2022
Full Text
View/download PDF

14. Online Non-Monotone DR-Submodular Maximization

Author

Thang, Nguyen Kim, Srivastav, Abhinav, Informatique, BioInformatique, Systèmes Complexes (IBISC), Université d'Évry-Val-d'Essonne (UEVE)-Université Paris-Saclay, and ANR-15-CE40-0015,OATA,Algorithmique en ligne au delà des approches traditionnelles(2015)

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Statistics - Machine Learning, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Machine Learning (stat.ML), General Medicine, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Machine Learning (cs.LG)
Abstract

In this paper, we study fundamental problems of maximizing DR-submodular continuous functions that have real-world applications in the domain of machine learning, economics, operations research and communication systems. It captures a subclass of non-convex optimization that provides both theoretical and practical guarantees. Here, we focus on minimizing regret for online arriving non-monotone DR-submodular functions over different types of convex sets: hypercube, down-closed and general convex sets. First, we present an online algorithm that achieves a $1/e$-approximation ratio with the regret of $O(T^{2/3})$ for maximizing DR-submodular functions over any down-closed convex set. Note that, the approximation ratio of $1/e$ matches the best-known guarantee for the offline version of the problem. Moreover, when the convex set is the hypercube, we propose a tight 1/2-approximation algorithm with regret bound of $O(\sqrt{T})$. Next, we give an online algorithm that achieves an approximation guarantee (depending on the search space) for the problem of maximizing non-monotone continuous DR-submodular functions over a \emph{general} convex set (not necessarily down-closed). To best of our knowledge, no prior algorithm with approximation guarantee was known for non-monotone DR-submodular maximization in the online setting. Finally we run experiments to verify the performance of our algorithms on problems arising in machine learning domain with the real-world datasets.

Published
2021

16. Online Non-preemptive Scheduling to Minimize Maximum Weighted Flow-time on Related Machines

Author

Lucarelli, Giorgio, Moseley, Benjamin, Nguyen, Kim Thang, Srivastav, Abhinav, Trystram, Denis, Laboratoire de Conception, Optimisation et Modélisation des Systèmes (LCOMS), Université de Lorraine (UL), Tepper School of Business, Carnegie Mellon University [Pittsburgh] (CMU), Informatique, BioInformatique, Systèmes Complexes (IBISC), Université d'Évry-Val-d'Essonne (UEVE), Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), and ANR-19-P3IA-0003,MIAI,MIAI @ Grenoble Alpes(2019)

Subjects
000 Computer science, knowledge, general works, Computer Science, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], ComputingMilieux_MISCELLANEOUS
Abstract

International audience; We consider the problem of scheduling jobs to minimize the maximum weighted flow-timeon a set of related machines. When jobs can be preempted this problem is well-understood; forexample, there exists a constant competitive algorithm using speed augmentation. When jobs mustbe scheduled non-preemptively, only hardness results are known. In this paper, we present thefirst online guarantees for the non-preemptive variant. We present the first constant competitivealgorithm for minimizing the maximum weighted flow-time on related machines by relaxing theproblem and assuming that the online algorithm can reject a small fraction of the total weight ofjobs. This is essentially the best result possible given the strong lower bounds on the non-preemptiveproblem without rejection.

Published
2019

19. Non-monotone DR-submodular Maximization: Approximation and Regret Guarantees

Author

D��rr, Christoph, Thang, Nguyen Kim, Srivastav, Abhinav, and Tible, L��o

Subjects
FOS: Computer and information sciences, TheoryofComputation_MISCELLANEOUS, Computer Science - Machine Learning, Optimization and Control (math.OC), Statistics - Machine Learning, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Data Structures and Algorithms (cs.DS), Machine Learning (stat.ML), Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract

Diminishing-returns (DR) submodular optimization is an important field with many real-world applications in machine learning, economics and communication systems. It captures a subclass of non-convex optimization that provides both practical and theoretical guarantees. In this paper, we study the fundamental problem of maximizing non-monotone DR-submodular functions over down-closed and general convex sets in both offline and online settings. First, we show that for offline maximizing non-monotone DR-submodular functions over a general convex set, the Frank-Wolfe algorithm achieves an approximation guarantee which depends on the convex set. Next, we show that the Stochastic Gradient Ascent algorithm achieves a 1/4-approximation ratio with the regret of $O(1/\sqrt{T})$ for the problem of maximizing non-monotone DR-submodular functions over down-closed convex sets. These are the first approximation guarantees in the corresponding settings. Finally we benchmark these algorithms on problems arising in machine learning domain with the real-world datasets.

Published
2019

20. Covering Clients with Types and Budgets

Author

Dimitris, Fotakis, Gourvès, Laurent, Mathieu, Claire, Srivastav, Abhinav, Corelab-NTUA-School of Electrical and Computer Engineering, National Technical University of Athens [Athens] (NTUA), Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL), Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), and gourves, laurent

Subjects
000 Computer science, knowledge, general works, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMilieux_MISCELLANEOUS
Abstract

In this paper, we consider a variant of the facility location problem. Imagine the scenario where facilities are categorized into multiple types such as schools, hospitals, post offices, etc. and the cost of connecting a client to a facility is realized by the distance between them. Each client has a total budget on the distance she/he is willing to travel. The goal is to open the minimum number of facilities such that the aggregate distance of each client to multiple types is within her/his budget. This problem closely resembles to the set cover and r-domination problems. Here, we study this problem in different settings. Specifically, we present some positive and negative results in the general setting, where no assumption is made on the distance values. Then we show that better results can be achieved when clients and facilities lie in a metric space.

Published
2018
Full Text
View/download PDF

21. Online Min-Sum Flow Scheduling with Rejections

Author

Lucarelli, Giorgio, Nguyen, Kim, Srivastav, Abhinav, Trystram, Denis, Data Aware Large Scale Computing (DATAMOVE ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Informatique, Biologie Intégrative et Systèmes Complexes (IBISC), Université d'Évry-Val-d'Essonne (UEVE), Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), VERIMAG (VERIMAG - IMAG), and Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])

Subjects
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; In this paper, we study the problems of preemptive and non-preemptive online scheduling of jobs on unrelated machines in order to minimize the average time a job remains in the system.Both problems are known to be non-approximable by a constant factor. However, the preemptive variant has been extensively studied under the different resource augmentation models. On the other hand, the non-preemptive variant is much less explored. An O( 1/epsilon )-competitive algorithm has been presented in [7] for the non-preemptive average flow-time minimization problem on a set of unrelated machines if bothan epsilon-speed augmentation is used and an epsilon-fraction of jobs is rejected. We are interested here in exploring the power of the rejection model and, mainly, in eliminating the need for speed augmentation in the latter result. On the road to this, we show how to replace speed augmentation with rejection in the preemptive variant. Our analysis is based on the dual-fitting paradigm.

Published
2017

22. Sur les aspects théoriques et pratiques des compromis dans les problèmes d'allocation des ressources

Author

Srivastav, Abhinav, STAR, ABES, VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Université Grenoble Alpes, Oded Maler, and Denis Trystram

Subjects
[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], Scheduling, Ordonnancement, Multi-Objective optimization, Resource augmentation, Optimisation multi-Objectifs, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Augmentation des ressources
Abstract

The content of this thesis is divided into two parts. The first part of the thesis deals with the study of heuristic based approaches for the approximation Pareto fronts. We propose a new Double Archive Pareto local search algorithm for solving multi-objective combinatorial optimization problems. We embed our technique into a genetic framework where our algorithm restarts with the set of new solutions formed by recombination and mutation of solutions found in the previous run. This method improves upon the existing Pareto local search algorithm for bi-objective and tri-objective quadratic assignment problem.In the second part of the thesis, we focus on non-preemptive scheduling algorithms. Here, we study the online problem of minimizing maximum stretch on a single machine. We present both positive and negative theoretical results. Then, we provide an optimally competitive semi-online algorithm. Furthermore, we study the problem of minimizing stretch on a single machine in a recently proposed rejection model. We show that there exists an O(1)-approximation ratio for minimizing average stretch. We also show that there exists an O(1)-approximation ratio for minimizing average flow time on a single machine. Lastly, we study the weighted average flow time minimization problem in online settings. We present a mathematical programming based framework that unifies multiple resource augmentation. Using the concept of duality, we show that there exists an O(1)-competitive algorithm for solving the weighted average flow time problem on unrelated machines. Furthermore, we proposed that this idea can be extended to minimizing l_k norms of weighted flow problem on unrelated machines., Le contenu de cette thèse est divisé en deux parties. La première partie de cette thèse porte sur l'étude d'approches heuristiques pour approximer des fronts de Pareto. Nous proposons un nouvel algorithme de recherche locale pour résoudre des problèmes d'optimisation combinatoire. Cette technique est intégrée dans un modèle opérationnel générique où l'algorithme évolue vers de nouvelles solutions formées en combinant des solutions trouvées dans les étapes précédentes. Cette méthode améliore les algorithmes de recherche locale existants pour résoudre le problème d'assignation quadratique bi- et tri-objectifs.La seconde partie se focalise sur les algorithmes d'ordonnancement dans un contexte non-préemptif. Plus précisément, nous étudions le problème de la minimisation du stretch maximum sur une seule machine pour une exécution online. Nous présentons des résultats positifs et négatifs, puis nous donnons une solution optimale semi-online. Nous étudions ensuite le problème de minimisation du stretch sur une seule machinedans le modèle récent de la réjection. Nous montrons qu'il existe un rapport d'approximation en O(1) pour minimiser le stretch moyen. Nous montrons également qu'il existe un résultat identique pour la minimisation du flot moyen sur une machine. Enfin, nous étudions le problème de la minimisation du somme des flots pondérés dans un contexte online.

Published
2017

24. Online Non-preemptive Scheduling in a Resource Augmentation Model based on Duality

Author

Lucarelli, Giorgio, Kim Thang, Nguyen, Srivastav, Abhinav, Trystram, Denis, Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Data Aware Large Scale Computing (DATAMOVE ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Informatique, Biologie Intégrative et Systèmes Complexes (IBISC), Université d'Évry-Val-d'Essonne (UEVE), and ANR-11-LABX-0025,PERSYVAL-lab,Systemes et Algorithmes Pervasifs au confluent des mondes physique et numérique(2011)

Subjects
Non-preemptive scheduling, 000 Computer science, knowledge, general works, ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Online algorithms, Resource augmentation, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Primal-dual algorithms, 010201 computation theory & mathematics, Computer Science, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing
Abstract

Resource augmentation is a well-established model for analyzing algorithms, particularly in the online setting. It has been successfully used for providing theoretical evidence for several heuristics in scheduling with good performance in practice. According to this model, the algorithm is applied to a more powerful environment than that of the adversary. Several types of resource augmentation for scheduling problems have been proposed up to now, including speed augmentation, machine augmentation and more recently rejection. In this paper, we present a framework that unifies the various types of resource augmentation. Moreover, it allows generalize the notion of resource augmentation for other types of resources. Our framework is based on mathematical programming and it consists of extending the domain of feasible solutions for the algorithm with respect to the domain of the adversary. This, in turn allows the natural concept of duality for mathematical programming to be used as a tool for the analysis of the algorithm's performance. As an illustration of the above ideas, we apply this framework and we propose a primal-dual algorithm for the online scheduling problem of minimizing the total weighted flow time of jobs on unrelated machines when the preemption of jobs is not allowed. This is a well representative problem for which no online algorithm with performance guarantee is known. Specifically, a strong lower bound of Omega(sqrt{n}) exists even for the offline unweighted version of the problem on a single machine. In this paper, we first show a strong negative result even when speed augmentation is used in the online setting. Then, using the generalized framework for resource augmentation and by combining speed augmentation and rejection, we present an (1+epsilon_s)-speed O(1/(epsilon_s epsilon_r))-competitive algorithm if we are allowed to reject jobs whose total weight is an epsilon_r-fraction of the weights of all jobs, for any epsilon_s > 0 and epsilon_r in (0,1). Furthermore, we extend the idea for analysis of the above problem and we propose an (1+\epsilon_s)-speed epsilon_r-rejection O({k^{(k+3)/k}}/{epsilon_{r}^{1/k}*epsilon_{s}^{(k+2)/k}})-competitive algorithm for the more general objective of minimizing the weighted l_k-norm of the flow times of jobs.

Published
2016

26. Online non-preemptive scheduling to optimize stretch

Author

Dutot, Pierre-François, Saule, Erik, Srivastav, Abhinav, Trystram, Denis, PrograMming and scheduling design fOr Applications in Interactive Simulation (MOAIS), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF), Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Department of Computer Science [Charlotte], College of Computing and Informatics [Charlotte], University of North Carolina [Charlotte] (UNC), University of North Carolina System (UNC)-University of North Carolina System (UNC)-University of North Carolina [Charlotte] (UNC), University of North Carolina System (UNC)-University of North Carolina System (UNC), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Laboratoire d'Informatique de Grenoble (LIG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience; no abstract

Published
2015

27. Competitive analysis for non-preemptive average stretch

Author

Srivastav, Abhinav, Trystram, Denis, PrograMming and scheduling design fOr Applications in Interactive Simulation (MOAIS), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF), Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Laboratoire d'Informatique de Grenoble (LIG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2014

Catalog

Books, media, physical & digital resources
See catalog results