Approximation Algorithms for Modern Multi-Processor Scheduling Problems
Graph Chatbot
Chattez avec Graph Search
Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.
AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.
In this paper, we study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. In short, we show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. In the ...
In chip multiprocessors (CMPs), limiting the number of off-chip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in which concurrently scheduled threads share a largely overlapp ...
It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contenti ...
We consider the comparative statics of solutions to parameterized optimization problems. A geometric method is developed for finding a vector field that, at each point in the parameter space, indicates a direction in which monotone comparative statics obta ...
In 1971, the first microprocessor produced in mass production had 2300 transistor and was able to compute 60'000 operations per second at 740 kHz. Nowadays, even a common gaming console uses a central unit including 243 millions of transistors running at 4 ...
The airline scheduling is a very large and complex problem. Moreover, it is common that only a minority of the initial schedules are carried out as planned because of delays, airport closures or other unforeseen events. Thus, given an actual state of the r ...
We propose a non-iterative solution to the PnP problem---the estimation of the pose of a calibrated camera from n 3D-to-2D point correspondences---whose computational complexity grows linearly with n. This is in contrast to state-of-the-art method that are ...
We consider the metric uncapacitated facility location problem(UFL). In this paper we modify the (1 + 2/e)-approximation algorithm of Chudak and Shmoys to obtain a new (1.6774,1.3738)- approximation algorithm for the UFL problem. Our linear programing roun ...
We propose a non-iterative solution to the PnP problem-the estimation of the pose of a calibrated camera from n 3D-to-2D point correspondences-whose computational complexity grows linearly with n. This is in contrast to state-of-the-art methods that are O( ...
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2007
It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contenti ...
