Technion web site Industrial Engineering and Management  
Hebrew     English
 
Home Faculty Research Courses & Programs Students Library Alumni About Us
 
 

Associate Professor Asaf Levin

 
 
General Information

Prof. Levin received his Ph.D. degree in operations research from Tel Aviv University, Tel Aviv, Israel (2003). From 2003 to  2004 he was a Postdoctoral Fellow at the Minerva Optimization Center, Technion, Haifa, Israel. Then, he joined the department of statistics in the Hebrew University of Jerusalem as a lecturer. Prof. Levin joined the Faculty of Industrial Engineering and Management in 2008 as a Senior Lecturer, and since 2011 he is an associate professor.

 

 
 
Research Summary

The research of Prof. Levin is focused on combinatorial optimization problems and on approximation algorithms for NP-hard optimization problems. The problems which he generally considers are from various application areas including network design, scheduling, covering and packing problems.


 
 
Selected Publications





  1. R. Hassin and A. Levin, ``Approximation algorithms for constructing wavelength routing networks'', Networks, 40, 32-37, 2002.



  2. R. Hassin and A. Levin, ``Graphs decomposable into two trees and k-edge-connected subgraphs'', Discrete Applied Mathematics, 126, 181-195, 2003.



  3. O. Goldschmidt, D.S. Hochbaum, A. Levin and E.V. Olinick, ``The SONET-edge partition problem'', Networks, 41, 13-23, 2003.



  4. R. Hassin and A. Levin, ``Minimum spanning tree with hop restrictions'', Journal of Algorithms, 48, 220-238, 2003.



  5. R. Hassin, A. Levin and D. Morad, ``Lexicographic local search and the p-center problem'', European Journal of Operational Research, 151, 265-279, 2003.



  6. R. Hassin and A. Levin, ``Minimum restricted diameter spanning trees'', Discrete Applied Mathematics, 137, 343-357, 2004. An extended abstract version of this paper appeared in Proc. APPROX 2002, 175-184, 2002.



  7. R. Hassin and A. Levin, "Synthesis of 2-commodity flow networks", Mathematics of Operations Research, 29, 280-288, 2004. An extended abstract version of this paper appeared in Proc. IPCO 2001, 226-235, 2001.



  8. R. Hassin and A. Levin, ``An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection'', SIAM Journal on Computing, 33, 261-268, 2004.



  9. A. Levin, ``A better approximation algorithm for the budget prize collecting tree problem,'' Operations Research Letters, 32, 316-319, 2004.



  10. A. Levin, ``A strongly polynomial-time approximation for a class of bicriteria problems'', Operations Research Letters, 32, 530-534, 2004.



  11. R. Hassin and A. Levin, ``Approximation algorithms for quickest spanning tree problem,'' Algorithmica, 41, 43-52, 2005. An extended abstract version appeared in Proc. ESA 2004.



  12. J. Konemann, A. Levin and A. Sinha, ``Approximating the degree bounded minimum diameter tree problem'', Algorithmica, 41, 117-129, 2005. An extended abstract version appeared in Proc. APPROX 2003, 109-121, 2003.



  13. R. Hassin and A. Levin, ``A better-than-greedy approximation algorithm for the minimum set cover problem", SIAM Journal on Computing, 35, 189-200, 2005. This paper was awarded as the best OR work for the year 2004 by the Israeli society of Operations Research, ORSIS.



  14. L. Epstein, A. Levin, "The chord version for SONET ADMs minimization", Theoretical Computer Science, 349, 337-346, 2005.



  15. R. Hassin and A. Levin, ``The minimum generalized vertex cover problem'', ACM/Transactions on Algorithms, 2, 66-78, 2006. An extended abstract version of this paper appeared in Proc. ESA 2003, 289-300, 2003.



  16. E. M. Arkin, R. Hassin and A. Levin, ``Approximations for min-max vehicle routing problems'', Journal of Algorithms, 59, 1-18, 2006.



  17. A. Levin and G. J. Woeginger, "The constrained minimum weighted sum of job completion times problem", Mathematical Programming, 108, 115-126, 2006. An extended abstract version appeared in Proc. IPCO 2004, 298-307, 2004.



  18. D.S. Hochbaum and A. Levin, "Optimizing over consecutive 1's and circular 1's constraints", SIAM Journal on Optimization, 17, 311-330, 2006.



  19. D.S. Hochbaum and A. Levin, "Methodologies and algorithms for group rankings decision", Management Science, 52, 1394-1408, 2006.



  20. D.S. Hochbaum and A. Levin, "Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms", Discrete Optimization, 3, 327-340, 2006.



  21. A. Levin, "Real time scheduling with a budget: Parametric-search is better than binary search", Information Processing Letters, 99, 187-191, 2006.



  22. L. Epstein and A. Levin, "The conference call search problem in wireless networks", Theoretical Computer Science, 359, 418-429, 2006. An extended abstract version appeared in Proc. WAOA 2005, 133-146, 2005.



  23. A. Levin and D. Segev, "Partial Multicuts in Trees", Theoretical Computer Science, 369, 384-395, 2006.



  24. L. Epstein and A. Levin, "SONET ADMs minimization with divisible paths", Algorithmica, 49, 51-68, 2007. An extended abstract version appeared in Proc. WAOA 2005, 119-132, 2005.



  25. E. Brosh, A. Levin and Y. Shavitt, "Approximation and heuristic algorithms for minimum delay application-layer multicast trees", IEEE/ACM Transactions on Networking, 15, 473-484, 2007.



  26. R. Hassin and A. Levin, "Flow trees for vertex-capacitated networks", Discrete Applied Mathematics, 155, 572-578, 2007.



  27. A. Levin, "The finite horizon investor problem with a budget constraint", Information Processing Letters, 104, 21-28, 2007.



  28. A. Levin, D. Paulusma and G. J. Woeginger, "The computational complexity of graph contractions I: polynomially solvable and NP-complete cases," Networks, 51, 178-189, 2008. An earlier version titled ``The complexity of graph contractions'', appeared in Proc. WG 2003, 322-333, 2003.  This paper and the next one were awarded the "2008 Glover-Klingman Prize for the best paper(s) of the year published in Networks".



  29. A. Levin, D. Paulusma and G. J. Woeginger, "The computational complexity of graph contractions II: two tough polynomially solvable cases," Networks, 52, 32-56, 2008.



  30. A. Archer, A. Levin and D. P. Williamson, ``Faster approximation algorithms for the minimum latency problem'', SIAM Journal on Computing, 37, 1472-1498, 2008. An earlier version appeared as Cornell OR&IE Technical report 1362.



  31. L. Epstein and A. Levin, "An APTAS for generalized cost variable sized bin packing," SIAM Journal on Computing, 38, 411-428, 2008.



  32. L. Epstein and A. Levin, ``A PTAS for delay minimization in establishing wireless conference calls", Discrete Optimization, 5, 88-96, 2008. An earlier extended abstract version appeared in Proc. of the 2nd WAOA (2004), 36-47.



  33. A. Levin and M. Penn, Approximation Algorithm for Minimizing Total Latency in Machine Scheduling with Deliveries, Discrete Optimization, 5, 97-107, 2008.



  34. L. Epstein and A. Levin, "More on online bin packing with two item sizes", Discrete Optimization, 5, 705-713, 2008.



  35. L. Epstein, A. Levin, R. van Stee, "Two dimensional packing with conflicts", ACTA Informatica, 45, 155-175, 2008. An earlier extended abstract version titled "Multi-dimensional Packing with Conflicts," appeared in Proc. FCT 2007, 288-299.



  36. L. Epstein, A. Levin and R. van Stee, "Online unit clustering: variations on a theme", Theoretical Computer Science, 407, 85-96, 2008.



  37. L. Epstein and A. Levin, "Asymptotic fully polynomial approximation schemes for variants of open-end bin packing," Information Processing Letters, 109, 32-37, 2008.



  38. L. Epstein and A. Levin, ``On bin packing with conflicts,'' SIAM Journal on Optimization, 19, 1270-1298, 2008. An earlier extended abstract version appeared in Proc. WAOA 2006, 160-173. 



  39. A. Levin, ``Approximating the unweighted k-set cover problem: greedy meets local search,'' SIAM Journal on Discrete Mathematics, 23, 251-264, 2008. An earlier extended abstract version appeared in Proc. WAOA 2006, 290-301. 



  40. L. Epstein, T. Erlebach, A. Levin, ``Variable Sized Online Interval Coloring with Bandwidth'', Algorithmica, 53, 385-401, 2009. An earlier extended abstract version appeared in Proc. SWAT 2006, 29-40.



  41. L. Epstein and A. Levin, ``A Robust APTAS for the Classical Bin Packing Problem'', Mathematical Programming, 119, 33-49, 2009. An earlier extended abstract version appeared in Proc. ICALP 2006, 214-225.



  42. D.S. Hochbaum and A. Levin "The multi-integer set cover and the facility terminal cover problem", Networks, 53, 63-66, 2009.



  43. L. Epstein, A. Levin, ``Better bounds for minimizing SONET ADMs", Journal on Computer and System Science, 75, 122-136, 2009. An earlier extended abstract version appeared in Proc. of the 2nd WAOA (2004), 281-294.



  44. L. Epstein, M. M. Halldorsson, A. Levin and H. Shachnai, ``Weighted sum coloring in batch scheduling of conflicting jobs'', Algorithmica, 55, 643-665, 2009. An earlier extended abstract version appeared in Proc. APPROX 2006, 116-127.



  45. A. Levin, G. Mosheiov and A. Sarig, "Scheduling a maintenance activity on parallel identical machines," Naval Research Logistics, 56, 33-41, 2009.



  46. J. R. Correa and A. Levin, ``Monotone covering problems with an additional covering constraint,'' Mathematics of Operations Research, 34, 238-248, 2009.



  47.  R. Hassin, A. Levin and S. Rubinstein, "Approximation algorithms for maximum latency and partial cycle cover," Discrete Optimization, 6, 197-205, 2009.



  48. A. Levin, "A generalized minimum cost k-clustering," ACM/Transactions on Algorithms, 5, 36:1-36:10, 2009.



  49. L. Epstein, T. Erlebach and A. Levin, "Online capacitated interval coloring,"  SIAM Journal on Discrete Mathematics, 23, 822-841, 2009.



  50. R. Hassin, A. Levin and M. Sviridenko, "Approximating the minimum quadratic assignment problems," ACM/Transactions on Algorithms, 6, 2009. 



  51. D.S. Hochbaum and A. Levin, "Covering the edges of bipartite graphs using $K_{2,2}$ graphs,"  Theoretical Computer Science, 411, 1-9, 2010.  An earlier extended abstract version appeared in Proc. WAOA 2007, 116-127.



  52. L. Epstein, C. Imreh and A. Levin, "Class constrained bin covering," Theory of Computing Systems, 46, 246-260, 2010.



  53. L. Epstein, A. Levin and B. Menahem, ``Minimization of SONET ADMs in ring networks revisited," accepted to Computing.



  54. L. Epstein, S. O. Krumke, A. Levin and H. Sperber, ``Selfish bin coloring," accepted to Journal of Combinatorial Optimization.



  55. J. Boyar, L. Epstein and A. Levin, ``Tight results for Next Fit and Worst Fit with resource augmentation," accepted to Theoretical Computer Science.



  56. L. Epstein and A. Levin ``Randomized algorithms for online bounded bidding," accepted to Information Processing Letters.



  57. J. Csirik, L. Epstein, Cs. Imreh and A. Levin "On the sum minimization version of the online bin covering problem," accepted to Discrete Applied Mathematics.



  58. L. Epstein,  C. Imreh and A. Levin, "Class constrained bin packing revisited," accepted to Theoretical Computer Science.



  59. L. Epstein and A. Levin, ""Improved randomized results for that interval selection problem,"  accepted to Theoretical Computer Science.



  60. L. Epstein, A. Levin and G.J. Woeginger, "Graph Coloring with Rejection," accepted to Journal on Computer and System Science.



  61. D. S. Hochbaum and A. Levin, "How to allocate review tasks for robust ranking," accepted to ACTA Informatica.



  62. L. Epstein and A. Levin, "Bin packing with general cost structures," accepted to Mathematical Programming.



Edit page


 
Return to the Faculty Members List Return to the main page
Home | Faculty | Research | Courses & Programs | Students | Library | Alumni | About UsTop of page
Copyright © 1998 - 2012  IEM faculty, Technion             Please, send your questions to webmaster  -  Israel Bravo         Disclaimer
http://ie.technion.ac.il         Total hits: 950182        Users online: 1                 Last updated at 10:05 - Monday Mar,26th, 2012