Asaf Levin

According to our database1, Asaf Levin authored at least 149 papers between 2002 and 2022.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.



In proceedings 
PhD thesis 




Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes.
Inf. Process. Lett., 2022

Starting time minimization for the maximum job variant.
Discret. Appl. Math., 2022

Cardinality Constrained Scheduling in Online Models.
CoRR, 2022

More on ordered open end bin packing.
J. Sched., 2021

Parameterized complexity of configuration integer programs.
Oper. Res. Lett., 2021

Complexity, algorithms and applications of the integer network flow with fractional supplies problem.
Oper. Res. Lett., 2021

EPTAS for parallel identical machine scheduling with time restrictions.
CoRR, 2021

A New Lower Bound for Classic Online Bin Packing.
Algorithmica, 2021

EPTAS for Load Balancing Problem on Parallel Machines with a Non-renewable Resource.
Proceedings of the Approximation and Online Algorithms - 19th International Workshop, 2021

Truly Asymptotic Lower Bounds for Online Vector Bin Packing.
Proceedings of the Approximation, 2021

A note on a variant of the online open end bin packing problem.
Oper. Res. Lett., 2020

Online bin packing with cardinality constraints resolved.
J. Comput. Syst. Sci., 2020

Algorithms and Complexity for Variants of Covariates Fine Balance.
CoRR, 2020

Truly asymptotic lower bounds for online vector bin packing.
CoRR, 2020

Deadline TSP.
Theor. Comput. Sci., 2019

Lower bounds for online bin covering-type problems.
J. Sched., 2019

Lower Bounds for Several Online Variants of Bin Packing.
Theory Comput. Syst., 2019

On the performance guarantee of First Fit for sum coloring.
J. Comput. Syst. Sci., 2019

Hypergraphic Degree Sequences are Hard.
Bull. EATCS, 2019

Robust algorithms for total completion time.
Discret. Optim., 2019

Multitype Integer Monoid Optimization and Applications.
CoRR, 2019

Approximation schemes for the generalized extensible bin packing problem.
CoRR, 2019

An Algorithmic Theory of Integer Programming.
CoRR, 2019

A Unified Framework for Designing EPTAS for Load Balancing on Parallel Machines.
Algorithmica, 2019

Online Bin Covering with Limited Migration.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Optimization over Degree Sequences.
SIAM J. Discret. Math., 2018

Online-bounded analysis.
J. Sched., 2018

The benefit of preemption with respect to the ℓp norm.
Oper. Res. Lett., 2018

Weighted matching with pair restrictions.
Optim. Lett., 2018

Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem.
J. Comb. Optim., 2018

Min-Sum Bin Packing.
J. Comb. Optim., 2018

Improved bounds for randomized preemptive online matching.
Inf. Comput., 2018

Discounted Reward TSP.
Algorithmica, 2018

Batch Coloring of Graphs.
Algorithmica, 2018

A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

A New and Improved Algorithm for Online Bin Packing.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

A Unified Framework for Designing EPTAS's for Load Balancing on Parallel Machines.
Proceedings of the Sailing Routes in the World of Computation, 2018

Power of Preemption for Minimizing Total Completion Time on Uniform Parallel Machines.
SIAM J. Discret. Math., 2017

An AFPTAS for variable sized bin packing with general activation costs.
J. Comput. Syst. Sci., 2017

Maximum coverage problem with group budget constraints.
J. Comb. Optim., 2017

On nonlinear multi-covering problems.
J. Comb. Optim., 2017

Approximate Shifted Combinatorial Optimization.
CoRR, 2017

Approximation Schemes for Makespan Minimization.
Encyclopedia of Algorithms, 2016

Shifted matroid optimization.
Oper. Res. Lett., 2016

The benefit of preemption for single machine scheduling so as to minimize total weighted completion time.
Oper. Res. Lett., 2016

A Unified Approach to Truthful Scheduling on Related Machines.
Math. Oper. Res., 2016

Vertex Cover Meets Scheduling.
Algorithmica, 2016

The benefit of adaptivity in stochastic packing problems with probing.
Theor. Comput. Sci., 2015

Offline black and white bin packing.
Theor. Comput. Sci., 2015

Min-max cover of a graph with a small number of parts.
Discret. Optim., 2015

Lexicographic Matroid Optimization.
CoRR, 2015

The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases.
Algorithmica, 2015

Online File Caching with Rejection Penalties.
Algorithmica, 2015

Adaptivity in the stochastic blackjack knapsack problem.
Theor. Comput. Sci., 2014

An efficient polynomial time approximation scheme for load balancing on uniformly related machines.
Math. Program., 2014

Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees.
J. Comb. Optim., 2014

Minimum total weighted completion time: Faster approximation schemes.
CoRR, 2014

Robust Algorithms for Preemptive Scheduling.
Algorithmica, 2014

Approximation Algorithms for a Minimization Variant of the Order-Preserving Submatrices and for Biclustering Problems.
ACM Trans. Algorithms, 2013

Robust Approximation Schemes for Cube Packing.
SIAM J. Optim., 2013

Nonoblivious 2-Opt heuristics for the traveling salesman problem.
Networks, 2013

The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature.
Discret. Optim., 2013

Bin covering with cardinality constraints.
Discret. Appl. Math., 2013

Online Clustering with Variable Sized Clusters.
Algorithmica, 2013

Improved Bounds for Online Preemptive Matching.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

On the max coloring problem.
Theor. Comput. Sci., 2012

Universal Sequencing on an Unreliable Machine.
SIAM J. Comput., 2012

Bin packing with general cost structures.
Math. Program., 2012

Approximation Schemes for Packing Splittable Items with Cardinality Constraints.
Algorithmica, 2012

On Equilibria for ADM Minimization Games.
Algorithmica, 2012

Uniform unweighted set cover: The power of non-oblivious local search.
Theor. Comput. Sci., 2011

Max-min Online Allocations with a Reordering Buffer.
SIAM J. Discret. Math., 2011

Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model.
SIAM J. Discret. Math., 2011

Graph coloring with rejection.
J. Comput. Syst. Sci., 2011

Selfish bin coloring.
J. Comb. Optim., 2011

Online variable-sized bin packing with conflicts.
Discret. Optim., 2011

On Variants of File Caching.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Covering the edges of bipartite graphs using K<sub>2, 2</sub> graphs.
Theor. Comput. Sci., 2010

Improved randomized results for the interval selection problem.
Theor. Comput. Sci., 2010

Class constrained bin packing revisited.
Theor. Comput. Sci., 2010

Tight results for Next Fit and Worst Fit with resource augmentation.
Theor. Comput. Sci., 2010

AFPTAS Results for Common Variants of Bin Packing: A New Method for Handling the Small Items.
SIAM J. Optim., 2010

Class Constrained Bin Covering.
Theory Comput. Syst., 2010

Randomized algorithms for online bounded bidding.
Inf. Process. Lett., 2010

On the sum minimization version of the online bin covering problem.
Discret. Appl. Math., 2010

Minimization of SONET ADMs in ring networks revisited.
Computing, 2010

How to allocate review tasks for robust ranking.
Acta Informatica, 2010

Finding mobile data under delay constraints with searching costs.
Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Universal Sequencing on a Single Machine.
Proceedings of the Integer Programming and Combinatorial Optimization, 2010

A generalized minimum cost <i>k</i>-clustering.
ACM Trans. Algorithms, 2009

Approximating the minimum quadratic assignment problems.
ACM Trans. Algorithms, 2009

Online Capacitated Interval Coloring.
SIAM J. Discret. Math., 2009

The multi-integer set cover and the facility terminal cover problem.
Networks, 2009

A robust APTAS for the classical bin packing problem.
Math. Program., 2009

Monotone Covering Problems with an Additional Covering Constraint.
Math. Oper. Res., 2009

Better bounds for minimizing SONET ADMs.
J. Comput. Syst. Sci., 2009

Approximation algorithms for maximum latency and partial cycle cover.
Discret. Optim., 2009

AFPTAS results for common variants of bin packing: A new method to handle the small items
CoRR, 2009

Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.
Algorithmica, 2009

Variable Sized Online Interval Coloring with Bandwidth.
Algorithmica, 2009

Online unit clustering: Variations on a theme.
Theor. Comput. Sci., 2008

On Bin Packing with Conflicts.
SIAM J. Optim., 2008

Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search.
SIAM J. Discret. Math., 2008

An APTAS for Generalized Cost Variable-Sized Bin Packing.
SIAM J. Comput., 2008

A Faster, Better Approximation Algorithm for the Minimum Latency Problem.
SIAM J. Comput., 2008

The computational complexity of graph contractions II: Two tough polynomially solvable cases.
Networks, 2008

The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases.
Networks, 2008

Asymptotic fully polynomial approximation schemes for variants of open-end bin packing.
Inf. Process. Lett., 2008

Approximation algorithm for minimizing total latency in machine scheduling with deliveries.
Discret. Optim., 2008

More on online bin packing with two item sizes.
Discret. Optim., 2008

A PTAS for delay minimization in establishing wireless conference calls.
Discret. Optim., 2008

Two-dimensional packing with conflicts.
Acta Informatica, 2008

Improved Randomized Results for That Interval Selection Problem.
Proceedings of the Algorithms, 2008

Approximation and heuristic algorithms for minimum-delay application-layer multicast trees.
IEEE/ACM Trans. Netw., 2007

The finite horizon investor problem with a budget constraint.
Inf. Process. Lett., 2007

Flow trees for vertex-capacitated networks.
Discret. Appl. Math., 2007

SONET ADMs Minimization with Divisible Paths.
Algorithmica, 2007

Covering the Edges of Bipartite Graphs Using <i>K</i> <sub>2, 2</sub> Graphs.
Proceedings of the Approximation and Online Algorithms, 5th International Workshop, 2007

Minimum Weighted Sum Bin Packing.
Proceedings of the Approximation and Online Algorithms, 5th International Workshop, 2007

Multi-dimensional Packing with Conflicts.
Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

Approximating min-max k-clustering.
Proceedings of the Fair Division, 24.06. - 29.06.2007, 2007

Partial multicuts in trees.
Theor. Comput. Sci., 2006

The conference call search problem in wireless networks.
Theor. Comput. Sci., 2006

The minimum generalized vertex cover problem.
ACM Trans. Algorithms, 2006

Optimizing over Consecutive 1's and Circular 1's Constraints.
SIAM J. Optim., 2006

The constrained minimum weighted sum of job completion times problem.
Math. Program., 2006

Methodologies and Algorithms for Group-Rankings Decision.
Manag. Sci., 2006

Approximations for minimum and min-max vehicle routing problems.
J. Algorithms, 2006

Real time scheduling with a budget: Parametric-search is better than binary search.
Inf. Process. Lett., 2006

Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms.
Discret. Optim., 2006

Approximating the Unweighted <i>k</i>-Set Cover Problem: Greedy Meets Local Search.
Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

The <i>k</i>-Allocation Problem and Its Variants.
Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

The chord version for SONET ADMs minimization.
Theor. Comput. Sci., 2005

A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem.
SIAM J. Comput., 2005

Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem.
Algorithmica, 2005

Approximation Algorithms for Quickest Spanning Tree Problems.
Algorithmica, 2005

An Approximation Algorithm for the Minimum Latency Set Cover Problem.
Proceedings of the Algorithms, 2005

Tracking mobile users.
Proceedings of the Algorithms for Optimization with Incomplete Information, 2005

An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection.
SIAM J. Comput., 2004

Strongly polynomial-time approximation for a class of bicriteria problems.
Oper. Res. Lett., 2004

A better approximation algorithm for the budget prize collecting tree problem.
Oper. Res. Lett., 2004

Synthesis of 2-Commodity Flow Networks.
Math. Oper. Res., 2004

Minimum restricted diameter spanning trees.
Discret. Appl. Math., 2004

The SONET edge-partition problem.
Networks, 2003

Minimum spanning tree with hop restrictions.
J. Algorithms, 2003

Lexicographic local search and the p.
Eur. J. Oper. Res., 2003

Subgraphs decomposable into two trees and k-edge-connected subgraphs.
Discret. Appl. Math., 2003

The Complexity of Graph Contractions.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

Approximation algorithms for constructing wavelength routing networks.
Networks, 2002