Search

Your search keyword '"LEVIN, ASAF"' showing total 632 results
Start Over Author "LEVIN, ASAF"
632 results on '"LEVIN, ASAF"'

101. The k-Allocation Problem and Its Variants

Author

Hochbaum, Dorit S., Levin, Asaf, 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, Erlebach, Thomas, editor, and Kaklamanis, Christos, editor

Published
2007
Full Text
View/download PDF

102. On Bin Packing with Conflicts

Author

Epstein, Leah, Levin, Asaf, 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, Erlebach, Thomas, editor, and Kaklamanis, Christos, editor

Published
2007
Full Text
View/download PDF

103. Graph Coloring with Rejection

Author

Epstein, Leah, Levin, Asaf, Woeginger, Gerhard J., 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, Azar, Yossi, editor, and Erlebach, Thomas, editor

Published
2006
Full Text
View/download PDF

104. Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs

Author

Epstein, Leah, Halldórsson, Magnús M., Levin, Asaf, Shachnai, Hadas, 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, Díaz, Josep, editor, Jansen, Klaus, editor, Rolim, José D. P., editor, and Zwick, Uri, editor

Published
2006
Full Text
View/download PDF

105. A Robust APTAS for the Classical Bin Packing Problem

Author

Epstein, Leah, Levin, Asaf, 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, Bugliesi, Michele, editor, Preneel, Bart, editor, Sassone, Vladimiro, editor, and Wegener, Ingo, editor

Published
2006
Full Text
View/download PDF

106. Variable Sized Online Interval Coloring with Bandwidth

Author

Epstein, Leah, Erlebach, Thomas, Levin, Asaf, 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, Arge, Lars, editor, and Freivalds, Rusins, editor

Published
2006
Full Text
View/download PDF

107. Partial Multicuts in Trees

Author

Levin, Asaf, Segev, Danny, 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, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Erlebach, Thomas, editor, and Persinao, Giuseppe, editor

Published
2006
Full Text
View/download PDF

108. SONET ADMs Minimization with Divisible Paths

Author

Epstein, Leah, Levin, Asaf, 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, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Erlebach, Thomas, editor, and Persinao, Giuseppe, editor

Published
2006
Full Text
View/download PDF

109. The Conference Call Search Problem in Wireless Networks

Author

Epstein, Leah, Levin, Asaf, 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, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Erlebach, Thomas, editor, and Persinao, Giuseppe, editor

Published
2006
Full Text
View/download PDF

110. An Approximation Algorithm for the Minimum Latency Set Cover Problem

Author

Hassin, Refael, Levin, Asaf, 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, Brodal, Gerth Stølting, editor, and Leonardi, Stefano, editor

Published
2005
Full Text
View/download PDF

111. A PTAS for Delay Minimization in Establishing Wireless Conference Calls

Author

Epstein, Leah, Levin, Asaf, 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, Persiano, Giuseppe, editor, and Solis-Oba, Roberto, editor

Published
2005
Full Text
View/download PDF

112. Better Bounds for Minimizing SONET ADMs

Author

Epstein, Leah, Levin, Asaf, 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, Persiano, Giuseppe, editor, and Solis-Oba, Roberto, editor

Published
2005
Full Text
View/download PDF

114. Approximation Algorithms for Quickest Spanning Tree Problems

Author

Hassin, Refael, Levin, Asaf, 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, Albers, Susanne, editor, and Radzik, Tomasz, editor

Published
2004
Full Text
View/download PDF

115. The Constrained Minimum Weighted Sum of Job Completion Times Problem

Author

Levin, Asaf, Woeginger, Gerhard J., Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., 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, Bienstock, Daniel, editor, and Nemhauser, George, editor

Published
2004
Full Text
View/download PDF

123. Cardinality Constrained Scheduling in Online Models

Author

Leah Epstein and Alexandra Lassota and Asaf Levin and Marten Maack and Lars Rohwedder, Epstein, Leah, Lassota, Alexandra, Levin, Asaf, Maack, Marten, Rohwedder, Lars, Leah Epstein and Alexandra Lassota and Asaf Levin and Marten Maack and Lars Rohwedder, Epstein, Leah, Lassota, Alexandra, Levin, Asaf, Maack, Marten, and Rohwedder, Lars

Abstract

Makespan minimization on parallel identical machines is a classical and intensively studied problem in scheduling, and a classic example for online algorithm analysis with Graham’s famous list scheduling algorithm dating back to the 1960s. In this problem, jobs arrive over a list and upon an arrival, the algorithm needs to assign the job to a machine. The goal is to minimize the makespan, that is, the maximum machine load. In this paper, we consider the variant with an additional cardinality constraint: The algorithm may assign at most k jobs to each machine where k is part of the input. While the offline (strongly NP-hard) variant of cardinality constrained scheduling is well understood and an EPTAS exists here, no non-trivial results are known for the online variant. We fill this gap by making a comprehensive study of various different online models. First, we show that there is a constant competitive algorithm for the problem and further, present a lower bound of 2 on the competitive ratio of any online algorithm. Motivated by the lower bound, we consider a semi-online variant where upon arrival of a job of size p, we are allowed to migrate jobs of total size at most a constant times p. This constant is called the migration factor of the algorithm. Algorithms with small migration factors are a common approach to bridge the performance of online algorithms and offline algorithms. One can obtain algorithms with a constant migration factor by rounding the size of each incoming job and then applying an ordinal algorithm to the resulting rounded instance. With this in mind, we also consider the framework of ordinal algorithms and characterize the competitive ratio that can be achieved using the aforementioned approaches. More specifically, we show that in both cases, one can get a competitive ratio that is strictly lower than 2, which is the bound from the standard online setting. On the other hand, we prove that no PTAS is possible.

Published
2022
Full Text
View/download PDF

129. Online Bounded Analysis

Author

Boyar, Joan, primary, Epstein, Leah, additional, Favrholdt, Lene M., additional, Larsen, Kim S., additional, and Levin, Asaf, additional

Published
2016
Full Text
View/download PDF

150. Truly Asymptotic Lower Bounds for Online Vector Bin Packing

Author

Balogh, János, Cohen, Ilan Reuven, Epstein, Leah, and Levin, Asaf

Subjects
Mathematics of computing → Approximation algorithms, online algorithms, Bin packing, vector packing, approximation algorithms, Mathematics of computing
Abstract

In this work, we consider online d-dimensional vector bin packing. It is known that no algorithm can have a competitive ratio of o(d/log² d) in the absolute sense, although upper bounds for this problem have always been presented in the asymptotic sense. Since variants of bin packing are traditionally studied with respect to the asymptotic measure, and since the two measures are different, we focus on the asymptotic measure and prove new lower bounds of the asymptotic competitive ratio. The existing lower bounds prior to this work were known to be smaller than 3, even for very large d. Here, we significantly improved on the best known lower bounds of the asymptotic competitive ratio (and as a byproduct, on the absolute competitive ratio) for online vector packing of vectors with d ≥ 3 dimensions, for every dimension d. To obtain these results, we use several different constructions, one of which is an adaptive construction with a lower bound of Ω(√d). Our main result is that the lower bound of Ω(d/log² d) on the competitive ratio holds also in the asymptotic sense. This result holds also against randomized algorithms, and requires a careful adaptation of constructions for online coloring, rather than simple black-box reductions., LIPIcs, Vol. 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), pages 8:1-8:18

Published
2021
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results