Publications

Publications

Publications

  • D. Amzallag, J. Naor and D. Raz, Algorithmic aspects of access network design in B3G/4G cellular networks, Proceedings of the 26th Annual IEEE Infocom Conference, Anchorage, Alaska (2007).
  • R. Engelberg and J. Naor, Equilibria in online games, Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA (2007).
  • N. Buchbinder and J. Naor, Improved bounds for online routing and packing via a primal-dual approach, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Berkeley, CA, (2006) pp. 293-304.
  • D. Amzallag, J. Naor and D. Raz, Coping with interferences: from maximum coverage to planning cellular networks, Proceedings of the 4th Workshop on Approximation and Online Algorithms (WAOA), Zurich, Switzerland, (2006).
  • N. Buchbinder and J. Naor, Fair online load balancing, Proceedings of the 18th ACM Symposium on Parallelism in Algorithms  and Architectures (SPAA), Cambridge, MA (2006), pp. 291-298.
  • C. Chekuri, J. Chuzhoy, L. Lewin-Eytan, J. Naor and A. Orda, Non-cooperative multicast and facility location games, Proceedings of the 7th ACM Conference on Electronic Commerce (EC), Ann Arbor, Michigan (2006), pp. 72-81.
  • R. Engelberg, J. Konemann, S. Leonardi and J. Naor, Cut problems in graphs with a budget constraint, Proceedings of the 7th Latin American Theoretical Informatics Symposium (LATIN), Valdivia, Chile (2006), pp. 435-446.
  • D. Amzallag, M. Livschitz, J. Naor and D. Raz, Cell planning of 4G cellular networks: algorithmic techniques, and results, Proceedings of the 6th IEE International Conference on3G & Beyond (3G ’2005) (2005), pp. 501-506.
  • Y. Bejerano, J. Naor and A. Sprintson, Efficient algorithms for shared backup allocation in networks with partial information, Proceedings of the 13th Annual European Symposium on Algorithms (ESA), Palma de Mallorca, Spain (2005), pp. 702-713.
  • N. Buchbinder and J. Naor, Online primal-dual algorithms for covering and packing problems, Proceedings of the 13th Annual European Symposium on Algorithms (ESA), Palma de Mallorca, Spain (2005), pp. 689-701.
  • R. Bhatia, N. Immorlica, T. Kimbrel, V. Mirrokni, J. Naor and B. Schieber, Traffic engineering of management flows by link augmentations on confluent trees, Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Las Vegas, Nevada (2005), pp. 289-298.
  • J. Naor and R. Schwartz, Balanced metric labeling, Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), Baltimore, Maryland (2005) pp. 582-591.
  • J. Naor, A. Rosen and G. Scalosub, Online time-constrained scheduling in linear networks, Proceedings of the 24th Annual IEEE Infocom Conference, Miami, Florida (2005).
  • N. Bansal, M. Charikar, S. Khanna and J. Naor, Approximating the average response time in broadcast scheduling, Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia (2005), pp. 215-221.
  • J. Chuzhoy, A. Gupta, J. Naor and A. Sinha, On the approximability of some network design problems, Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia (2005), pp. 943-951.
  • J. Chuzhoy and J. Naor,  S. Guha, S. Khanna, and J. Naor, Machine minimization for scheduling jobs with interval constraints, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Rome, Italy (2004), pp. 81-90.
  • J. Chuzhoy and J. Naor, The hardness of metric labeling, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Rome, Italy (2004), pp. 108-114.
  • J. Chuzhoy, S. Guha, E. Halperin, S. Khanna, G. Kortsarz, and J. Naor, Asymmetric k-Center is log*n hard to approximate, Proceedings of the 36th Annual ACM Symposiumon Theory of Computing (STOC), Chicago, Illinois (2004), pp. 21-27.
  • J. Chuzhoy and J. Naor, New hardness results for congestion minimization and machine scheduling,  Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), Chicago, Illinois (2004), pp. 28-34.
  • N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder and J. Naor, A general approach to online network optimization problems, Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, Louisiana (2004), pp. 570-579.
  • J. Naor and R. Schwartz, The directed circular arrangement problem, Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, Louisiana (2004), pp 86-95.
  • N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder and J. Naor, The online set cover problem, Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), San Diego, California (2003), pp. 100-105.
  • R. Bhatia, J. Chuzhoy, A. Freund, and J. Naor, Algorithmic aspects of bandwidth trading,  Proceedings of the 30th International Colloquium on Automata,Languages, and Programming (ICALP), Eindhoven, The Netherlands (2003), pp. 751-766.
  • C. Chekuri, S. Guha and J. Naor, Approximating Steiner k-cuts, Proceedings of the 30th International Colloquium on Automata,Languages, and Programming (ICALP), Eindhoven, The Netherlands (2003), pp. 189-199.
  • J. Naor, H. Shachnai and T. Tamir, Real-time scheduling with a budget, Proceedings of the 30th International Colloquium on Automata,Languages, and Programming (ICALP), Eindhoven, The Netherlands (2003), pp. 1123-1137.
  • Y. Bejerano, N. Immorlica, J. Naor and M. Smith, Efficient location area planning for personal communication systems, Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MOBICOM), San Diego, California (2003), pp. 109-121. To appear: ACM-IEEE Transactions on Networking.
  •  J. Chuzhoy and J. Naor, Covering problems with hard capacities, Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Vancouver, Canada (2002), pp. 481-489.
  • L. Lewin-Eytan, J. Naor and A. Orda, Routing and admission control in networks with advance reservations, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), Rome, Italy (2002), pp. 215-228.
  • S. Khanna, J. Naor and D. Raz, Control message aggregation in group communication protocols, Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP), Malaga, Spain (2002), pp. 135-146.
  • C. Chekuri, A. Gupta, A. Kumar, J. Naor and D. Raz, Building edge-failure resilient networks, Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO), Cambridge, Massachusetts (2002), pp. 439-456.
  • A. Freund and J. Naor, Approximating the advertisement placement problem, Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO), Cambridge, Massachusetts (2002), pp. 415-424.
  • J. Garay, J. Naor, B. Yener and P. Zhao, On-line admission control and packet scheduling with interleaving,  Proceedings of the 21st Annual IEEE Infocom Conference, New York, NY (2002).
  • A. Bar-Noy, S. Guha, Y. Katz, J. Naor, H. Shachnai and B. Schieber, Throughput maximization of real-time scheduling with batching, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, California (2002), pp. 742-751.
  • R. Bar-Yehuda, M. M. Halldorsson, J. Naor, H. Shachnai and I. Shapira, Scheduling split intervals, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, California (2002), pp. 732-741.
  • A. Bar-Noy, A. Freund, S. Landa and J. Naor, Competitive on-line switching policies, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, California (2002), pp. 525-534.
  • C. Chekuri, S. Khanna and J. Naor, A deterministic algorithm for the cost-distance problem,  Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Washington, DC (2001), pp. 232-233.
  • J. Naor and Y. Rabani, Tree packing and approximating k-cuts, Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Washington DC (2001), pp. 26-27.
  • C. Chekuri, S. Khanna, J. Naor and L. Zosin, Approximation algorithms for the metric labeling problem via a new linear programming formulation, Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Washington DC (2001), pp. 109-118.
  • R. Bar-Yehuda, G. Even, J. Feldman and J. Naor, Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems, Journal of Graph Algorithms and Applications, Vol. 5 (2001), pp. 1-27.
  • Y. Bejerano, I. Cidon and J. Naor, Dynamic session management for static and mobile users: a competitive on-line algorithmic approach, Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (Dial M for Mobility), Boston, Massachusetts (2000), pp 65-74.
  • A. Bar-Noy, J. Naor and B. Schieber, Pushing dependent data in clients-providers-servers systems, Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (Mobicom), Boston, Massachusetts (2000), pp. 222-230. To appear: IEEE Journal on Selected Areas in Communications, Wireless Communications Series.
  • A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor and B. Schieber, A unified approach to approximating resource allocation and scheduling, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), Portland, Oregon (2000), pp. 735-744.
  • Y. Bejerano, I. Cidon and J. Naor, Efficient handoff rerouting algorithms: a competitive on-line algorithmic approach, Proceedings of the 19th Annual IEEE Infocom Conference, Tel Aviv, Israel (2000), pp. 198–207.
  • M. Charikar, J. Naor and B. Schieber, Resource optimization in QoS multicast routing of real-time multimedia, Proceedings of the 19th Annual IEEE Infocom Conference, Tel Aviv, Israel (2000), pp. 1518–1527.
  • S. Khanna, J. Naor and F. B. Shepherd, Directed network design with orientation constraints, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, California (2000), pp. 663–671.
  • A. Bar-Noy, A. Freund, J. Naor, On-line load balancing in a hierarchical server topology, Proceedings of the 7th Annual European Symposium on Algorithms (ESA), Prague, Czech Republic
  • S. Guha, A. Moss, J. Naor, and B. Schieber, Efficient recovery from power outage, Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), Atlanta, Georgia (1999), pp. 574–582.
  •  A. Bar-Noy, S. Guha, J. Naor, and B. Schieber, Approximating the throughput of multiple machines in real-time scheduling,  Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), Atlanta, Georgia (1999), pp. 622–631.
  • Y. Azar, R. Motwani and J. Naor, Approximating arbitrary probability distributions using small sample spaces, Combinatorica, Vol. 18 (1998), pp. 151-171.
  • S. Khuller, A. Moss and J. Naor, The budgeted maximum coverage problem, Information Processing Letters, Vol. 70 (1999), pp. 39-45.
  • A. Bar-Noy, S. Guha, J. Naor, and B.. Schieber, Multicasting in heterogeneous networks,  Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), Dallas, Texas (1998), pp. 448–453.
  • A. Bar-Noy, R. Bhatia, J. Naor, and B. Schieber, Minimizing service and operation costs of periodic scheduling,  Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, California (1998), pp. 11–20.
  • J. Naor and L. Zosin, A 2-approximation algorithm for the directed multiway cut problem, Proceedings of the 38th Conference on Foundations of Computer Science (FOCS), Miami Beach, Florida (1997), pp. 548–553.
  • J. Naor, A. Orda and Y. Petruschka, Dynamic storage allocation with known durations, Proceedings of the 5th Annual European Symposium on Algorithms (ESA), Graz, Austria 1997, pp. 378–387.
  • G. Even, J. Naor, S. Rao and B.. Schieber, Fast approximate graph partitioning algorithms,  Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, Louisiana (1997), pp. 639-648.
  • G. Even, J. Naor and L. Zosin, An 8-Approximation algorithm for the subset feedback vertex set problem,  Proceedings of the 37th IEEE Conference on Foundations of Computer Science (FOCS), Burlington, Vermont (1996), pp. 310-319.
  • G. Even, J. Naor, B. Schieber and L. Zosin, Approximating minimum subset feedback sets in undirected graphs with applications to multicuts, 4th Israeli Symposium on Theory of Computing and Systems (ISTCS), Jerusalem, Israel (1996), pp. 78-88.
  • J. Naor and D. Hochbaum, Approximation algorithms for network design problems on bounded subsets,  Journal of Algorithms, Vol. 21 (1996), pp. 403-414.
  • G. Even, J. Naor, B. Schieber and S. Rao, Divide-and-conquer approximation algorithms via spreading metrics, Proceedings of the 36th IEEE Conference on Foundations of Computer Science (FOCS), Milwaukee, Wisconsin (1995), pp. 62-71.
  • R. Bhatia, S. Khuller and J. Naor, The loading time scheduling problem, Proceedings of the 36th IEEE Conference on Foundations of Computer Science (FOCS), Milwaukee, Wisconsin (1995),
  • G.  Even, J. Naor, B. Schieber and M. Sudan, Approximating Minimum Feedback Sets and Multicuts in Directed Graphs,  Proceedings of the 4th Conference on Integer Programming and Combinatorial Optimization (IPCO), Copenhagen, Denmark (1995), pp. 14-28.
  • J. Naor, A. Orda and R. Rom, Scheduled hot-potato routing, Proceedings of the 14th Annual IEEE Infocom Conference, Boston, Massachusetts (1995), pp. 579-586.
  • J. Naor and R. M. Roth, Constructions of permutation arrays for certain scheduling cost measures,  Random Structures and Algorithms, Vol. 6 (1995), pp. 39-50.
  • R. Bar-Yehuda, D. Geiger, J. Naor and R. M. Roth, Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and bayesian inference, Proceedings of
    the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, Virginia (1994), pp. 344-354.
  • Michael Luby, J. Naor, Ariel Orda, Tight bounds for dynamic storage allocation, Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, Virginia (1994), pp. 724-732.
  • D. Hochbaum, N. Megiddo, J. Naor and A. Tamir, Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality, Mathematical Programming, Vol. 62 (1993), pp. 69-83. (Festschrift in honor of Philip Wolfe).
  • S. Khuller, J. Naor, and P. Klein, The lattice structure of planar flow, SIAM Journal on Discrete Mathematics,  Vol. 6 (1993), pp. 477-490.
  • N. Alon, J. Bruck, J. Naor, M. Naor and R. M. Roth, Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs, IEEE Transactions on Information Theory,  Vol. 38 (1992), pp. 509-516.
  • A. Bar-Noy, R. Motwani and J. Naor, The greedy algorithm is optimal for on-line edge coloring, Information Processing Letters, Vol. 44 (1992), pp. 251-253.
  • Y. Azar, J. Naor and R. Rom, Routing strategies for fast networks, Proceedings of the 11th Annual IEEE Infocom Conference, Florence, Italy (1992), pp. 170-179.
  •  D. Hochbaum and J. Naor, Simple and fast algorithms for linear and integer programs with two variables per inequality, Proceedings of the 2nd Conference on Integer Programming and Combinatorial Optimization (IPCO), Pittsburgh, PA (1992), pp. 44-59.
  • Y. Azar, J. Naor and Raphael Rom, The competitiveness of online assignments, Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Orlando, Florida (1992), pp. 203-210.
  • Samir Khuller and J. Naor, Flow in planar graphs with vertex capacities, Proceedings of the 1st Conference on Integer Programming and Combinatorial Optimization (IPCO), Waterloo (1990), pp. 367-383.
  • J. Naor and M. Naor, Small bias probability spaces: efficient constructions and applications, Proceedings of the 22nd Annual ACM Symposium on Theory of Computation (STOC), Baltimore, MD (1990), pp. 213-223.
  • A. Bar-Noy and J. Naor, Sorting, minimal feedback sets and Hamilton paths in tournaments, SIAM Journal on Discrete Mathematics, Vol. 3 (1990), pp. 7-20.
  • J. Naor and M. Novick, An efficient reconstruction of a graph from its line graph in parallel, Journal of Algorithms, Vol. 11 (1990), pp. 132-143.
  • G. L. Miller and J. Naor, Flow in planar graphs with multiple sources and sinks, Proceedings of the 30th IEEE Conference on Foundations of Computer Science (FOCS), St. Louis, MI (1989), pp. 112-117.
  • R. Motwani, J. Naor and M. Naor, The probabilistic method yields deterministic parallel algorithms,  Proceedings of the 30th IEEE Conference on Foundations of Computer Science (FOCS), St. Louis, MI (1989), pp. 8-13.
  • M. Chrobak, J. Naor and M. Novick, Using bounded degree spanning trees in the design of efficient algorithms on claw free graphs,  Workshop on Algorithms and Data Structures (WADS), Carleton University (1989). Springer Verlag Lecture Notes in Computer Science 382, pp. 147-162.
  • M. Chrobak and J. Naor, An efficient parallel algorithm for computing a large independent set in a planar graph, Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), (1989), pp. 379-387.
  • E. Gafni, J. Naor and P. Ragde, On separating the EREW and CREW PRAM models, Theoretical Computer Science, Vol. 68 (1989), pp. 343-346.
  • A. Bar-Noy, J. Naor and Moni Naor, One bit algorithms, Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (PODC), Toronto (1988), pp. 66-74.
  • J. Naor, Perfect matchings in line graphs, Aegean Workshop on computing, 3rd International Workshop on Parallel Computation and VLSI Theory, Corfu Island, Greece, (1988), pp. 139-148.
  • M. Karchmer and J. Naor, A fast parallel algorithm for coloring a graph with D colors, Journal of Algorithms, Vol. 9 (1988), pp. 83-91.
  • J. Naor, M. Naor and A. A. Schaffer, Fast parallel algorithms for chordal graphs, Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), New York, NY (1987), pp. 355-364.
  • J. Naor, A fast parallel algorithm for coloring a planar graph with five colors, Information Processing Letters, Vol. 25 (1987), pp. 51-53.
  • S. Peleg, J. Naor, R. Hartley and D. Avnir, Multiple resolution texture analysis and classification,  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 6 (1984), pp. 518-523.
  • J. Naor and S. Peleg, Hierarchical image representation for compression, filtering and normalization,  Pattern Recognition Letters, Vol. 2 (1983), pp. 43-46.
  • J. Naor and S. Peleg, Image compression and filtering using pyramid data structures, International Joint Conference on Artificial Intelligence, (IJCAI), Karlsruhe (1983), pp. 1086-1088.

 

Chapters in Books (Refereed)

  • Samir Khuller and J. Naor, Flow in planar graphs: a survey of recent results. In: Planar Graphs,
    DIMACS Series in Discrete Math and Theoretical Computer Science, (Edited by William T. Trotter),
    Vol 9, 1993, pp. 59-84.
  • R. Motwani, J. Naor and P. Raghavan, Randomized Approximation Algorithms in
    Combinatorial Optimization. In: Approximation Algorithms for NP-Hard Problems, Edited by Dorit S.
    Hochbaum, PWS Publishing Company, 1996.
  • Y. Bejerano, I. Cidon and J. Naor, Competitive analysis of handoff rerouting algorithm. In:
    Mobile and Wireless Internet Protocols, Algorithms and Systems, Edited by Kia Makki, Niki Pissinou,
    Kami (Sam) Makki, and E.K. Park, pp. 263-304, Kluwer Academic Publishers, Boston, 2003.