Search

Your search keyword '"Widmayer, Peter"' showing total 20 results
Start Over Author "Widmayer, Peter" Topic competitive ratio

Refine your results

more »

more »

20 results on '"Widmayer, Peter"'

1. Online Train Disposition: To Wait or Not to Wait?

Author

Anderegg, Luzi, Penna, Paolo, Widmayer, Peter, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ahuja, Ravindra K., editor, Möhring, Rolf H., editor, and Zaroliagis, Christos D., editor

Published
2009
Full Text
View/download PDF

2. Discovery of Network Properties with All-Shortest-Paths Queries

Author

Bilò, Davide, Erlebach, Thomas, Mihalák, Matúš, Widmayer, Peter, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Shvartsman, Alexander A., editor, and Felber, Pascal, editor

Published
2008
Full Text
View/download PDF

3. Online Delay Management on a Single Train Line

Author

Gatto, Michael, Jacob, Riko, Peeters, Leon, Widmayer, Peter, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Geraets, Frank, editor, Kroon, Leo, editor, Schoebel, Anita, editor, Wagner, Dorothea, editor, and Zaroliagis, Christos D., editor

Published
2007
Full Text
View/download PDF

4. On the Robustness of Graham’s Algorithm for Online Scheduling

Author

Gatto, Michael, Widmayer, Peter, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dehne, Frank, editor, Sack, Jörg-Rüdiger, editor, and Zeh, Norbert, editor

Published
2007
Full Text
View/download PDF

5. Online Single Machine Batch Scheduling

Author

Gfeller, Beat, Peeters, Leon, Weber, Birgitta, Widmayer, Peter, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Královič, Rastislav, editor, and Urzyczyn, Paweł, editor

Published
2006
Full Text
View/download PDF

6. An Algorithmic View on OVSF Code Assignment

Author

Erlebach, Thomas, Jacob, Riko, Mihaľák, Matúš, Nunkesser, Marc, Szabó, Gábor, Widmayer, Peter, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Diekert, Volker, editor, and Habib, Michel, editor

Published
2004
Full Text
View/download PDF

8. Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms

Author

Hromkovič, Juraj, Mömke, Tobias, Steinhöfel, Kathleen, and Widmayer, Peter

Subjects
Datavetenskap (datalogi), Social Sciences and Humanities, Makespan, Multiple machines, online algorithms, Computer Sciences, Scheduling, job shop scheduling, Sciences Humaines et Sociales, Online Algorithms, Approximation Algorithms, Competitive ratio
Abstract

We consider the job shop scheduling problem unit-J_m, where each job is processed once on each of m given machines. Every job consists of a permutation of tasks for all machines. The execution of any task on its corresponding machine takes exactly one time unit. The objective is to minimize the overall completion time, called makespan. The contributionof this paper are the following results: (i) For any input instance ofunit-J_m with d jobs, the makespan of an optimum schedule is at most m + o(m), for d = o(m^{1/2}). This improves on the upper bound O(m + d) given in [LMR99] where O hides a constant equal to two as shown in [S98]. For d=2 the upper bound is improved to m + \lceil \sqrt{m} \rceil. (ii) There exist input instances of unit-J_m with d = 2 such that themakespan of an optimum schedule is at least m+ \lceil \sqrt{m} \rceil, i.e., our upper bound for d=2, see result (i), cannot be improved. (iii) We present a randomized on-line approximation algorithm for unit-J_m with the best known approximation ratio for d = o(m^{1/2}). (iv) There is no deterministic on-line algorithm with a competitive ratiobetter than 4/3 for unit-J_m with two jobs, and for three or more jobs,there is no deterministic on-line algorithm which is better than 1.5competitive. Compared with the expected competitive ratio of (iii) whichtends to 1, this shows that for unit-J_m randomization is very powerfulcompared with determinism. For two and three jobs, deterministic on-linealgorithms with competitive ratios tending to 4/3 and 1.5 respectivelyare presented. (v) A deterministic approximation algorithm for unit-J_mis described that works in quadratic time for constant $d$ and has anapproximation ratio of 1 + 2^d/\lfloor \sqrt{m} \rfloor for d \leq 2 \log_2 m. QC 20101005

9. Optimal Online Edge Coloring of Planar Graphs with Advice

Author

Mikkelsen, Jesper W., 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, Paschos, Vangelis Th., editor, and Widmayer, Peter, editor

Published
2015
Full Text
View/download PDF

10. Competitive Analysis of the Windfall Game

Author

Fleischer, Rudolf, Zhang, Tao, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Ferro, Alfredo, editor, Luccio, Fabrizio, editor, and Widmayer, Peter, editor

Published
2014
Full Text
View/download PDF

11. Walking in Streets with Minimal Sensing

Author

Tabatabaei, Azadeh, Ghodsi, Mohammad, Hutchison, David, Serieseditor, Kanade, Takeo, Serieseditor, Kittler, Josef, Serieseditor, Kleinberg, Jon M., Serieseditor, Mattern, Friedemann, Serieseditor, Mitchell, John C., Serieseditor, Naor, Moni, Serieseditor, Nierstrasz, Oscar, Serieseditor, Pandu Rangan, C., Serieseditor, Steffen, Bernhard, Serieseditor, Sudan, Madhu, Serieseditor, Terzopoulos, Demetri, Serieseditor, Tygar, Doug, Serieseditor, Vardi, Moshe Y., Serieseditor, Weikum, Gerhard, Serieseditor, Widmayer, Peter, editor, Xu, Yinfeng, editor, and Zhu, Binhai, editor

Published
2013
Full Text
View/download PDF

12. Online Bin Packing with (1,1) and (2,R) Bins

Author

Chen, Jing, Han, Xin, Iwama, Kazuo, Ting, Hing-Fung, Hutchison, David, Serieseditor, Kanade, Takeo, Serieseditor, Kittler, Josef, Serieseditor, Kleinberg, Jon M., Serieseditor, Mattern, Friedemann, Serieseditor, Mitchell, John C., Serieseditor, Naor, Moni, Serieseditor, Nierstrasz, Oscar, Serieseditor, Pandu Rangan, C., Serieseditor, Steffen, Bernhard, Serieseditor, Sudan, Madhu, Serieseditor, Terzopoulos, Demetri, Serieseditor, Tygar, Doug, Serieseditor, Vardi, Moshe Y., Serieseditor, Weikum, Gerhard, Serieseditor, Widmayer, Peter, editor, Xu, Yinfeng, editor, and Zhu, Binhai, editor

Published
2013
Full Text
View/download PDF

13. Online Bin Covering: Expectations vs. Guarantees

Author

Christ, Marie G., Favrholdt, Lene M., Larsen, Kim S., Hutchison, David, Serieseditor, Kanade, Takeo, Serieseditor, Kittler, Josef, Serieseditor, Kleinberg, Jon M., Serieseditor, Mattern, Friedemann, Serieseditor, Mitchell, John C., Serieseditor, Naor, Moni, Serieseditor, Nierstrasz, Oscar, Serieseditor, Pandu Rangan, C., Serieseditor, Steffen, Bernhard, Serieseditor, Sudan, Madhu, Serieseditor, Terzopoulos, Demetri, Serieseditor, Tygar, Doug, Serieseditor, Vardi, Moshe Y., Serieseditor, Weikum, Gerhard, Serieseditor, Widmayer, Peter, editor, Xu, Yinfeng, editor, and Zhu, Binhai, editor

Published
2013
Full Text
View/download PDF

14. Online Sum-Radii Clustering

Author

Fotakis, Dimitris, Koutris, Paraschos, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Rovan, Branislav, editor, Sassone, Vladimiro, editor, and Widmayer, Peter, editor

Published
2012
Full Text
View/download PDF

15. Approximate Discovery of Random Graphs

Author

Erlebach, Thomas, Hall, Alexander, Mihal’ák, Matúš, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Hromkovič, Juraj, editor, Královič, Richard, editor, Nunkesser, Marc, editor, and Widmayer, Peter, editor

Published
2007
Full Text
View/download PDF

16. Preemptive Scheduling in Overloaded Systems

Author

Chrobak, Marek, Epstein, Leah, Noga, John, Sgall, Jiří, van Stee, Rob, Tichý, Tomáš, Vakhania, Nodari, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Widmayer, Peter, editor, Eidenbenz, Stephan, editor, Triguero, Francisco, editor, Morales, Rafael, editor, Conejo, Ricardo, editor, and Hennessy, Matthew, editor

Published
2002
Full Text
View/download PDF

17. Scheduling Search Procedures

Author

Damaschke, Peter, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Widmayer, Peter, editor, Eidenbenz, Stephan, editor, Triguero, Francisco, editor, Morales, Rafael, editor, Conejo, Ricardo, editor, and Hennessy, Matthew, editor

Published
2002
Full Text
View/download PDF

19. Control Message Aggregation in Group Communication Protocols

Author

Khanna, Sanjeev, Naor, Joseph Seffi, Raz, Dan, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Widmayer, Peter, editor, Eidenbenz, Stephan, editor, Triguero, Francisco, editor, Morales, Rafael, editor, Conejo, Ricardo, editor, and Hennessy, Matthew, editor

Published
2002
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results