10 Search Results for "Kim Thang, Nguyen"

Document
DOI: 10.4230/LIPIcs.ISAAC.2020.45
Online Primal-Dual Algorithms with Configuration Linear Programs

Authors: Nguyễn Kim Thắng

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
In this paper, we present primal-dual algorithms for online problems with non-convex objectives. Problems with convex objectives have been extensively studied in recent years where the analyses rely crucially on the convexity and the Fenchel duality. However, problems with non-convex objectives resist against current approaches and non-convexity represents a strong barrier in optimization in general and in the design of online algorithms in particular. In our approach, we consider configuration linear programs with the multilinear extension of the objectives. We follow the multiplicative weight update framework in which a novel point is that the primal update is defined based on the gradient of the multilinear extension. We introduce new notions, namely (local) smoothness, in order to characterize the competitive ratios of our algorithms. The approach leads to competitive algorithms for several problems with convex/non-convex objectives.
Cite as

Nguyễn Kim Thắng. Online Primal-Dual Algorithms with Configuration Linear Programs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{thang:LIPIcs.ISAAC.2020.45,
  author =	{Thắng, Nguy\~{ê}n Kim},
  title =	{{Online Primal-Dual Algorithms with Configuration Linear Programs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{45:1--45:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.45},
  URN =		{urn:nbn:de:0030-drops-133891},
  doi =		{10.4230/LIPIcs.ISAAC.2020.45},
  annote =	{Keywords: Configuration Linear Programs, Primal-Dual, Smoothness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.84
An Improved Approximation Algorithm for Scheduling Under Arborescence Precedence Constraints

Authors: Nguyễn Kim Thắng

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We consider a scheduling problem on unrelated machines with precedence constraints. There are m unrelated machines and n jobs and every job has to be processed non-preemptively in some machine. Moreover, jobs have precedence constraints; specifically, a precedence constraint j ≺ j' requires that job j' can only be started whenever job j has been completed. The objective is to minimize the total completion time. The problem has been widely studied in more restricted machine environments such as identical or related machines. However, for unrelated machines, much less is known. In the paper, we study the problem where the precedence constraints form a forest of arborescences. We present a O((log n)² / (log log n)³)-approximation algorithm - that improves the best-known guarantee of O((log n)² / log log n) due to Kumar et al. a decade ago. The analysis relies on a dual-fitting method in analyzing the Lagrangian function of non-convex programs.
Cite as

Nguyễn Kim Thắng. An Improved Approximation Algorithm for Scheduling Under Arborescence Precedence Constraints. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 84:1-84:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{thang:LIPIcs.MFCS.2020.84,
  author =	{Thắng, Nguy\~{ê}n Kim},
  title =	{{An Improved Approximation Algorithm for Scheduling Under Arborescence Precedence Constraints}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{84:1--84:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.84},
  URN =		{urn:nbn:de:0030-drops-127459},
  doi =		{10.4230/LIPIcs.MFCS.2020.84},
  annote =	{Keywords: Scheduling, Precedence Constraints, Lagrangian Duality}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.24
Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines

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

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

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

Giorgio Lucarelli, Benjamin Moseley, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 24:1-24:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lucarelli_et_al:LIPIcs.FSTTCS.2019.24,
  author =	{Lucarelli, Giorgio and Moseley, Benjamin and Thang, Nguyen Kim and Srivastav, Abhinav and Trystram, Denis},
  title =	{{Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{24:1--24:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.24},
  URN =		{urn:nbn:de:0030-drops-115867},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.24},
  annote =	{Keywords: Online Algorithms, Scheduling, Resource Augmentation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.39
A Competitive Algorithm for Random-Order Stochastic Virtual Circuit Routing

Authors: Thắng Nguyễn Kim

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We consider the virtual circuit routing problem in the stochastic model with uniformly random arrival requests. In the problem, a graph is given and requests arrive in a uniform random order. Each request is specified by its connectivity demand and the load of a request on an edge is a random variable with known distribution. The objective is to satisfy the connectivity request demands while maintaining the expected congestion (the maximum edge load) of the underlying network as small as possible. Despite a large literature on congestion minimization in the deterministic model, not much is known in the stochastic model even in the offline setting. In this paper, we present an O(log n/log log n)-competitive algorithm when optimal routing is sufficiently congested. This ratio matches to the lower bound Omega(log n/ log log n) (assuming some reasonable complexity assumption) in the offline setting. Additionally, we show that, restricting on the offline setting with deterministic loads, our algorithm yields the tight approximation ratio of Theta(log n/log log n). The algorithm is essentially greedy (without solving LP/rounding) and the simplicity makes it practically appealing.
Cite as

Thắng Nguyễn Kim. A Competitive Algorithm for Random-Order Stochastic Virtual Circuit Routing. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 39:1-39:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{nguyenkim:LIPIcs.ISAAC.2019.39,
  author =	{Nguy\~{ê}n Kim, Thắng},
  title =	{{A Competitive Algorithm for Random-Order Stochastic Virtual Circuit Routing}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{39:1--39:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.39},
  URN =		{urn:nbn:de:0030-drops-115351},
  doi =		{10.4230/LIPIcs.ISAAC.2019.39},
  annote =	{Keywords: Approximation Algorithms, Congestion Minimization}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.66
Game Efficiency Through Linear Programming Duality

Authors: Nguyen Kim Thang

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
The efficiency of a game is typically quantified by the price of anarchy (PoA), defined as the worst ratio of the value of an equilibrium - solution of the game - and that of an optimal outcome. Given the tremendous impact of tools from mathematical programming in the design of algorithms and the similarity of the price of anarchy and different measures such as the approximation and competitive ratios, it is intriguing to develop a duality-based method to characterize the efficiency of games. In the paper, we present an approach based on linear programming duality to study the efficiency of games. We show that the approach provides a general recipe to analyze the efficiency of games and also to derive concepts leading to improvements. The approach is particularly appropriate to bound the PoA. Specifically, in our approach the dual programs naturally lead to competitive PoA bounds that are (almost) optimal for several classes of games. The approach indeed captures the smoothness framework and also some current non-smooth techniques/concepts. We show the applicability to the wide variety of games and environments, from congestion games to Bayesian welfare, from full-information settings to incomplete-information ones.
Cite as

Nguyen Kim Thang. Game Efficiency Through Linear Programming Duality. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 66:1-66:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kimthang:LIPIcs.ITCS.2019.66,
  author =	{Kim Thang, Nguyen},
  title =	{{Game Efficiency Through Linear Programming Duality}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{66:1--66:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.66},
  URN =		{urn:nbn:de:0030-drops-101597},
  doi =		{10.4230/LIPIcs.ITCS.2019.66},
  annote =	{Keywords: Price of Anarchy, Primal-Dual}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.59
Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines

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

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
In this paper, we consider the online problem of scheduling independent jobs 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. However, the problem in the non-preemptive setting admits a strong lower bound. Recently, Lucarelli et al. presented an algorithm that achieves a O(1/epsilon^2)-competitive ratio when the algorithm is allowed to reject epsilon-fraction of total weight of jobs and has an 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(1/epsilon^3)-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.
Cite as

Giorgio Lucarelli, Benjamin Moseley, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lucarelli_et_al:LIPIcs.ESA.2018.59,
  author =	{Lucarelli, Giorgio and Moseley, Benjamin and Thang, Nguyen Kim and Srivastav, Abhinav and Trystram, Denis},
  title =	{{Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{59:1--59:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.59},
  URN =		{urn:nbn:de:0030-drops-95226},
  doi =		{10.4230/LIPIcs.ESA.2018.59},
  annote =	{Keywords: Online Algorithms, Scheduling, Resource Augmentation}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.30
A Greedy Algorithm for Subspace Approximation Problem

Authors: Nguyen Kim Thang

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
In the subspace approximation problem, given m points in R^{n} and an integer k <= n, the goal is to find a k-dimension subspace of R^{n} that minimizes the l_{p}-norm of the Euclidean distances to the given points. This problem generalizes several subspace approximation problems and has applications from statistics, machine learning, signal processing to biology. Deshpande et al. [Deshpande et al., 2011] gave a randomized O(sqrt{p})-approximation and this bound is proved to be tight assuming NP != P by Guruswami et al. [Guruswami et al., 2016]. It is an intriguing question of determining the performance guarantee of deterministic algorithms for the problem. In this paper, we present a simple deterministic O(sqrt{p})-approximation algorithm with also a simple analysis. That definitely settles the status of the problem in term of approximation up to a constant factor. Besides, the simplicity of the algorithm makes it practically appealing.
Cite as

Nguyen Kim Thang. A Greedy Algorithm for Subspace Approximation Problem. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 30:1-30:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{thang:LIPIcs.SWAT.2018.30,
  author =	{Thang, Nguyen Kim},
  title =	{{A Greedy Algorithm for Subspace Approximation Problem}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{30:1--30:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.30},
  URN =		{urn:nbn:de:0030-drops-88562},
  doi =		{10.4230/LIPIcs.SWAT.2018.30},
  annote =	{Keywords: Approximation Algorithms, Subspace Approximation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.12
Online Algorithms for Multi-Level Aggregation

Authors: Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Vesely

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests. Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4*2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. We include several additional results in the paper. We show that a standard lower-bound technique for MLAP, based on so-called Single-Phase instances, cannot give super-constant lower bounds (as a function of the tree depth). This result is established by giving an online algorithm with optimal competitive ratio 4 for such instances on arbitrary trees. We also study the MLAP variant when the tree is a path, for which we give a lower bound of 4 on the competitive ratio, improving the lower bound known for general MLAP. We complement this with a matching upper bound for the deadline setting.
Cite as

Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Vesely. Online Algorithms for Multi-Level Aggregation. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.ESA.2016.12,
  author =	{Bienkowski, Marcin and B\"{o}hm, Martin and Byrka, Jaroslaw and Chrobak, Marek and D\"{u}rr, Christoph and Folwarczny, Lukas and Jez, Lukasz and Sgall, Jiri and Kim Thang, Nguyen and Vesely, Pavel},
  title =	{{Online Algorithms for Multi-Level Aggregation}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.12},
  URN =		{urn:nbn:de:0030-drops-63637},
  doi =		{10.4230/LIPIcs.ESA.2016.12},
  annote =	{Keywords: algorithmic aspects of networks, online algorithms, scheduling and resource allocation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.63
Online Non-Preemptive Scheduling in a Resource Augmentation Model Based on Duality

Authors: Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

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.
Cite as

Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-Preemptive Scheduling in a Resource Augmentation Model Based on Duality. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 63:1-63:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{lucarelli_et_al:LIPIcs.ESA.2016.63,
  author =	{Lucarelli, Giorgio and Kim Thang, Nguyen and Srivastav, Abhinav and Trystram, Denis},
  title =	{{Online Non-Preemptive Scheduling in a Resource Augmentation Model Based on Duality}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{63:1--63:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.63},
  URN =		{urn:nbn:de:0030-drops-64047},
  doi =		{10.4230/LIPIcs.ESA.2016.63},
  annote =	{Keywords: Online algorithms, Non-preemptive scheduling, Resource augmentation, Primal-dual}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.20
Lagrangian Duality based Algorithms in Online Energy-Efficient Scheduling

Authors: Nguyen Kim Thang

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
We study online scheduling problems in the general energy model of speed scaling with power down. The latter is a combination of the two extensively studied energy models, speed scaling and power down, toward a more realistic one. Due to the limits of the current techniques, only few results have been known in the general energy model in contrast to the large literature of the previous ones. In the paper, we consider a Lagrangian duality based approach to design and analyze algorithms in the general energy model. We show the applicability of the approach to problems which are unlikely to admit a convex relaxation. Specifically, we consider the problem of minimizing energy with a single machine in which jobs arrive online and have to be processed before their deadlines. We present an alpha^alpha-competitive algorithm (whose the analysis is tight up to a constant factor) where the energy power function is of typical form z^alpha + g for constants alpha > 2 and g non-negative. Besides, we also consider the problem of minimizing the weighted flow-time plus energy. We give an O(alpha/ln(alpha))-competitive algorithm; that matches (up to a constant factor) to the currently best known algorithm for this problem in the restricted model of speed scaling.
Cite as

Nguyen Kim Thang. Lagrangian Duality based Algorithms in Online Energy-Efficient Scheduling. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kimthang:LIPIcs.SWAT.2016.20,
  author =	{Kim Thang, Nguyen},
  title =	{{Lagrangian Duality based Algorithms in Online Energy-Efficient Scheduling}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.20},
  URN =		{urn:nbn:de:0030-drops-60427},
  doi =		{10.4230/LIPIcs.SWAT.2016.20},
  annote =	{Keywords: Online Scheduling, Energy Minimization, Speed Scaling and Power-down, Lagrangian Duality}
}
  • Refine by Author
  • 4 Kim Thang, Nguyen
  • 3 Lucarelli, Giorgio
  • 3 Srivastav, Abhinav
  • 3 Thang, Nguyen Kim
  • 3 Trystram, Denis
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Scheduling algorithms
  • 1 Theory of computation → Algorithmic game theory and mechanism design
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 3 Scheduling
  • 2 Approximation Algorithms
  • 2 Lagrangian Duality
  • 2 Online Algorithms
  • 2 Primal-Dual
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 3 2016
  • 3 2019
  • 2 2018
  • 2 2020

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