My Papers:
Journal papers:
R. Hassin and A. Levin, ``Approximation algorithms for constructing wavelength routing networks'', Networks, 40, 32-37, 2002.
R. Hassin and A. Levin, ``Graphs decomposable into two trees and k-edge-connected subgraphs'', Discrete Applied Mathematics, 126, 181-195, 2003.
O. Goldschmidt, D.S. Hochbaum, A. Levin and E.V. Olinick, ``The SONET-edge partition problem'', Networks, 41, 13-23, 2003.
R. Hassin and A. Levin, ``Minimum spanning tree with hop restrictions'', Journal of Algorithms, 48, 220-238, 2003.
R. Hassin, A. Levin and D. Morad, ``Lexicographic local search and the p-center problem'', European Journal of Operational Research, 151, 265-279, 2003.
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.
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.
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.
A. Levin, ``A better approximation algorithm for the budget prize collecting tree problem,'' Operations Research Letters, 32, 316-319, 2004.
A. Levin, ``A strongly polynomial-time approximation for a class of bicriteria problems'', Operations Research Letters, 32, 530-534, 2004.
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.
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.
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.
L. Epstein, A. Levin, "The chord version for SONET ADMs minimization", Theoretical Computer Science, 349, 337-346, 2005.
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.
E. M. Arkin, R. Hassin and A. Levin, ``Approximations for min-max vehicle routing problems'', Journal of Algorithms, 59, 1-18, 2006.
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.
D.S. Hochbaum and A. Levin, "Optimizing over consecutive 1's and circular 1's constraints", SIAM Journal on Optimization, 17, 311-330, 2006.
D.S. Hochbaum and A. Levin, "Methodologies and algorithms for group rankings decision", Management Science, 52, 1394-1408, 2006.
D.S. Hochbaum and A. Levin, "Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms", to appear in Discrete Optimization .
A. Levin, "Real time scheduling with a budget: Parametric-search is better than binary search", Information Processing Letters, 99, 187-191, 2006.
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.
A. Levin and D. Segev, "Partial Multicuts in Trees", Theoretical Computer Science, 369, 384-395, 2006.
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.
R. Hassin and A. Levin, "Flow trees for vertex-capacitated networks", Discrete Applied Mathematics, 155, 572-578, 2007.
A. Levin, "The finite horizon investor problem with a budget constraint", Information Processing Letters, 104, 21-28, 2007.
A. Levin, D. Paulusma and G. J. Woeginger, "The computational complexity of graph contractions I: polynomially solvable and NP-complete cases," to appear in Networks. An earlier version titled ``The complexity of graph contractions'', appeared in Proc. WG 2003, 322-333, 2003.
A. Levin, D. Paulusma and G. J. Woeginger, "The computational complexity of graph contractions II: two tough polynomially solvable cases," to appear in Networks.
A. Levin, "A generalized minimum cost k-clustering," to appear in ACM/Transactions on Algorithms.
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.
L. Epstein and A. Levin, "An APTAS for generalized cost variable sized bin packing," SIAM Journal on Computing, 38, 411-428, 2008.
L. Epstein, T. Erlebach, A. Levin, ``Variable Sized Online Interval Coloring with Bandwidth'', to appear in Algorithmica. An earlier extended abstract version appeared in Proc. SWAT 2006, 29-40.
L. Epstein and A. Levin, ``A Robust APTAS for the Classical Bin Packing Problem'', to appear in Mathematical Programming. An earlier extended abstract version appeared in Proc. ICALP 2006, 214-225.
L. Epstein and A. Levin, A PTAS for delay minimization in establishing wireless conference calls, to appear in Discrete Optimization. An earlier extended abstract version appeared in Proc. of the 2nd WAOA (2004), 36-47.
A. Levin and M. Penn, Approximation Algorithm for Minimizing Total Latency in Machine Scheduling with Deliveries, to appear in Discrete Optimization.
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.
D.S. Hochbaum and A. Levin "The multi-integer set cover and the facility terminal cover problem", to appear in Networks.
L. Epstein, A. Levin, Better bounds for minimizing SONET ADMs , to appear in Journal on Computer and System Science. An earlier extended abstract version appeared in Proc. of the 2nd WAOA (2004), 281-294.
L. Epstein, M. M. Halldorsson, A. Levin and H. Shachnai, ``Weighted sum coloring in batch scheduling of conflicting jobs'', to appear in Algorithmica. An earlier extended abstract version appeared in Proc. APPROX 2006, 116-127.
L. Epstein and A. Levin, ``On bin packing with conflicts,'' accepted to SIAM Journal on Optimization. An earlier extended abstract version appeared in Proc. WAOA 2006, 160-173.
L. Epstein and A. Levin, "More on online bin packing with two item sizes", accepted to Discrete Optimization.
L. Epstein, A. Levin and R. van Stee, "Online unit clustering: variations on a theme", accepted to Theoretical Computer Science.
L. Epstein, C. Imreh and A. Levin, "Class constrained bin covering,'' accepted to Theory of Computing Systems.
L. Epstein and A. Levin, "Asymptotic fully polynomial approximation schemes for variants of open-end bin packing," accepted to Information Processing Letters.
A. Levin, G. Mosheiov and A. Sarig, "Scheduling a maintenance activity on parallel identical machines," accepted to Naval Research Logistics (and additional tables file).
J. R. Correa and A. Levin, ``Monotone covering problems with an additional covering constraint,'' accepted to Mathematics of Operations Research.
A. Levin, ``Approximating the unweighted k-set cover problem: greedy meets local search,'' accepted to SIAM Journal on Discrete Mathematics. An earlier extended abstract version appeared in Proc. WAOA 2006, 290-301.
Papers in refereed conference proceedings:
R. Hassin and A. Levin, ``An approximation algorithm for the minimum latency set cover problem", Proc. ESA 2005.
L. Epstein, A. Levin and G. J. Woeginger, ``Graph coloring with rejection'', Proc. ESA 2006, 364-375.
D. S. Hochbaum and A. Levin, ``The k-allocation problem and its variants,'' Proc. WAOA 2006, 253-264.
D.S. Hochbaum and A. Levin, "Covering the edges of bipartite graphs using K_{2,2} graphs," to appear in Proc. WAOA 2007.
L. Epstein and A. Levin, "On the max coloring problem," appear in Proc. WAOA 2007.
L. Epstein and A. Levin, "Minimum weighted sum bin packing," appear in Proc. WAOA 2007.
L. Epstein and A. Levin, "Improved randomized results for that interval selection problem," accepted to Proc. ESA 2008.