Nguyen Kim Thang

Nguyen Kim Thang

Auto-generated profile, based on publicly available information

Nguyen Kim Thang

Univ Évry, Université Paris-Saclay

Research Focus & Metrics

Academic Career Length

13Years (2014-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
16 January 2016 in Journal of Scheduling
Verified
Journal Article
Closed access
PDF file
NBNikhil Bansal
Nikhil Bansal
CDChristoph Dürr
Christoph Dürr
NTNguyen Kim Thang
Nguyen Kim Thang
ÓVÓscar C. Vásquez
Óscar C. Vásquez


12 February 2014 in Journal of Combinatorial Optimization
Verified
Journal Article
Closed access
PDF file
EAEric Angel
Eric Angel
NTNguyen Kim Thang
Nguyen Kim Thang
DRDamien Regnault
Damien Regnault

13 March 2018
Verified
Book Chapter
Closed access
PDF file
VCVincent Chau
Vincent Chau
SFShengzhong Feng
Shengzhong Feng
NTNguyen Kim Thang
Nguyen Kim Thang

22 August 2017 in arXiv
Verified
Preprint
Open access
PDF file
NTNguyen Kim Thang
Nguyen Kim Thang
The efficiency of a game is typically quantified by the price of anarchy (PoA), defined as the worst ratio of the objective function 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.

28 February 2018 in arXiv
Verified
Preprint
Open access
PDF file
GLGiorgio Lucarelli
Giorgio Lucarelli
BMBenjamin Moseley
Benjamin Moseley
NTNguyen Kim Thang
Nguyen Kim Thang
ASAbhinav Srivastav
Abhinav Srivastav
DTDenis Trystram
Denis Trystram
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.