Joseph Naor

Niv Buchbinder, Joseph Naor: Fair online load balancing. J. Scheduling 16(1): 117-127 (2013)

Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor: A Greedy Approximation Algorithm for Minimum-Gap Scheduling. CIAC 2013: 97-109

Nikhil Bansal, Niv Buchbinder, Joseph Naor: A Primal-Dual Randomized Algorithm for Weighted Paging. J. ACM 59(4): 19 (2012)

Niv Buchbinder, Shahar Chen, Joseph Naor, Ohad Shamir: Unified Algorithms for Online Learning and Competitive Analysis. Journal of Machine Learning Research - Proceedings Track 23: 5.1-5.18 (2012)

Edward Bortnikov, Samir Khuller, Jian Li, Yishay Mansour, Joseph Naor: The load-distance balancing problem. Networks 59(1): 22-29 (2012)

Nikhil Bansal, Niv Buchbinder, Joseph Naor: Randomized Competitive Algorithms for Generalized Caching. SIAM J. Comput. 41(2): 391-414 (2012)

Niv Buchbinder, Liane Lewin-Eytan, Ishai Menache, Joseph Naor, Ariel Orda: Dynamic Power Allocation Under Arbitrary Varying Channels - An Online Approach. IEEE/ACM Trans. Netw. 20(2): 477-487 (2012)

Niv Buchbinder, Moran Feldman, Joseph Naor, Roy Schwartz: A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization. FOCS 2012: 649-658

Niv Buchbinder, Joseph Naor, R. Ravi, Mohit Singh: Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints. ICALP (1) 2012: 145-156

Navendu Jain, Ishai Menache, Joseph Naor, F. Bruce Shepherd: Topology-Aware VM Migration in Bandwidth Oversubscribed Datacenter Networks. ICALP (2) 2012: 586-597

Navendu Jain, Ishai Menache, Joseph Naor, Jonathan Yaniv: Near-optimal scheduling mechanisms for deadline-sensitive jobs in large computing clusters. SPAA 2012: 255-266

Moran Feldman, Liane Lewin-Eytan, Joseph Naor: Hedonic clustering games. SPAA 2012: 267-276

Niv Buchbinder, Joseph Naor, R. Ravi, Mohit Singh: Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints. CoRR abs/1205.1477 (2012)

Moran Feldman, Joseph Naor, Roy Schwartz: Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract). APPROX-RANDOM 2011: 218-229

Moran Feldman, Joseph Naor, Roy Schwartz, Justin Ward: Improved Approximations for k-Exchange Systems - (Extended Abstract). ESA 2011: 784-798

Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz: Min-max Graph Partitioning and Small Set Expansion. FOCS 2011: 17-26

Joseph Naor, Debmalya Panigrahi, Mohit Singh: Online Node-Weighted Steiner Tree and Related Problems. FOCS 2011: 210-219

Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph Naor: A Polylogarithmic-Competitive Algorithm for the k-Server Problem. FOCS 2011: 267-276

Moran Feldman, Joseph Naor, Roy Schwartz: A Unified Continuous Greedy Algorithm for Submodular Maximization. FOCS 2011: 570-579

Moran Feldman, Joseph Naor, Roy Schwartz: Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm - (Extended Abstract). ICALP (1) 2011: 342-353

Navendu Jain, Ishai Menache, Joseph Naor, Jonathan Yaniv: A Truthful Mechanism for Value-Based Scheduling in Cloud Computing. SAGT 2011: 178-189

Niv Buchbinder, Moran Feldman, Arpita Ghosh, Joseph Naor: Frequency Capping in Online Advertising. WADS 2011: 147-158

Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph Naor: A Polylogarithmic-Competitive Algorithm for the k-Server Problem. CoRR abs/1110.1580 (2011)

Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz: Min-Max Graph Partitioning and Small Set Expansion. CoRR abs/1110.4319 (2011)

Joseph Naor, Adi Rosén, Gabriel Scalosub: Online time-constrained scheduling in linear and ring networks. J. Discrete Algorithms 8(4): 346-355 (2010)

Niv Buchbinder, Liane Lewin-Eytan, Joseph Naor, Ariel Orda: Non-Cooperative Cost Sharing Games via Subsidies. Theory Comput. Syst. 47(1): 15-37 (2010)

Joseph Naor, Roy Schwartz: The directed circular arrangement problem. ACM Transactions on Algorithms 6(3) (2010)

Nikhil Bansal, Kamal Jain, Anna Kazeykina, Joseph Naor: Approximation Algorithms for Diversified Search Ranking. ICALP (2) 2010: 273-284

Nikhil Bansal, Niv Buchbinder, Joseph Naor: Metrical Task Systems and the k-Server Problem on HSTs. ICALP (1) 2010: 287-298

Moran Feldman, Joseph Naor: Non-Preemptive Buffer Management for Latency Sensitive Packets. INFOCOM 2010: 186-190

Niv Buchbinder, Liane Lewin-Eytan, Ishai Menache, Joseph Naor, Ariel Orda: Dynamic Power Allocation Under Arbitrary Varying Channels - The Multi-User Case. INFOCOM 2010: 2402-2410

Nikhil Bansal, Niv Buchbinder, Joseph Naor: Towards the Randomized k-Server Conjecture: A Primal-Dual Approach. SODA 2010: 40-55

Niv Buchbinder, Joseph Naor: The Design of Competitive Online Algorithms via a Primal-Dual Approach. Foundations and Trends in Theoretical Computer Science 3(2-3): 93-263 (2009)

Niv Buchbinder, Joseph Naor: Online Primal-Dual Algorithms for Covering and Packing. Math. Oper. Res. 34(2): 270-286 (2009)

Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor: The Online Set Cover Problem. SIAM J. Comput. 39(2): 361-370 (2009)

Lap Chi Lau, Joseph Naor, Mohammad R. Salavatipour, Mohit Singh: Survivable Network Design with Degree or Order Constraints. SIAM J. Comput. 39(3): 1062-1087 (2009)

Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Naor, Baruch Schieber, Hadas Shachnai: Throughput maximization of real-time scheduling with batching. ACM Transactions on Algorithms 5(2) (2009)

Niv Buchbinder, Liane Lewin-Eytan, Ishai Menache, Joseph Naor, Ariel Orda: Dynamic Power Allocation Under Arbitrary Varying Channels - An Online Approach. INFOCOM 2009: 145-153

Joseph Naor, Danny Raz, Gabriel Scalosub: Toward Optimal Utilization of Shared Random Access Channels. INFOCOM 2009: 2061-2069

Robert Krauthgamer, Joseph Naor, Roy Schwartz: Partitioning graphs into balanced components. SODA 2009: 942-949

Irit Dinur, Klaus Jansen, Joseph Naor, José D. P. Rolim (Eds.): Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings. Lecture Notes in Computer Science 5687, Springer 2009, isbn 978-3-642-03684-2

Irith Ben-Arroyo Hartman, Seffi Naor, Michal Penn, Uriel G. Rothblum: The Third Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms. Discrete Applied Mathematics 156(4): 407-408 (2008)

Irith Ben-Arroyo Hartman, Seffi Naor, Michal Penn, Uriel G. Rothblum: Editorial. Discrete Applied Mathematics 156(4): 410-411 (2008)

Randeep Bhatia, Nicole Immorlica, Tracy Kimbrel, Vahab S. Mirrokni, Joseph Naor, Baruch Schieber: Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees. Theory Comput. Syst. 42(1): 2-26 (2008)

Julia Chuzhoy, Anupam Gupta, Joseph Naor, Amitabh Sinha: On the approximability of some network design problems. ACM Transactions on Algorithms 4(2) (2008)

Niv Buchbinder, Liane Lewin-Eytan, Joseph Naor, Ariel Orda: Non-cooperative Cost Sharing Games Via Subsidies. SAGT 2008: 337-349

Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks: Online multicast with egalitarian cost sharing. SPAA 2008: 70-76

Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, Roy Schwartz: Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. STOC 2008: 11-20

Nikhil Bansal, Niv Buchbinder, Joseph Naor: Randomized competitive algorithms for generalized caching. STOC 2008: 235-244

Joseph Naor, Danny Raz, Gabriel Scalosub: Homogeneous Interference Game in Wireless Networks. WINE 2008: 514-521

Joseph Naor, Hadas Shachnai, Tami Tamir: Real-Time Scheduling with a Budget. Algorithmica 47(3): 343-364 (2007)

Roee Engelberg, Jochen Könemann, Stefano Leonardi, Joseph Naor: Cut problems in graphs with a budget constraint. J. Discrete Algorithms 5(2): 262-279 (2007)

Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Joseph Naor, Ariel Orda: Non-Cooperative Multicast and Facility Location Games. IEEE Journal on Selected Areas in Communications 25(6): 1193-1206 (2007)

Julia Chuzhoy, Joseph Naor: The Hardness of Metric Labeling. SIAM J. Comput. 36(5): 1376-1386 (2007)

Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor: Algorithmic aspects of bandwidth trading. ACM Transactions on Algorithms 3(1) (2007)

Niv Buchbinder, Kamal Jain, Joseph Naor: Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue. ESA 2007: 253-264

Nikhil Bansal, Niv Buchbinder, Anupam Gupta, Joseph Naor: An O (log² k )-Competitive Algorithm for Metric Bipartite Matching. ESA 2007: 522-533

Nikhil Bansal, Niv Buchbinder, Joseph Naor: A Primal-Dual Randomized Algorithm for Weighted Paging. FOCS 2007: 507-517

David Amzallag, Joseph Naor, Danny Raz: Algorithmic Aspects of Access Networks Design in B3G/4G Cellular Networks. INFOCOM 2007: 991-999

Liane Lewin-Eytan, Joseph Naor, Ariel Orda: Maximum-lifetime routing: system optimization & game-theoretic perspectives. MobiHoc 2007: 160-169

Roee Engelberg, Joseph Naor: Equilibria in online games. SODA 2007: 149-158

Lap Chi Lau, Joseph Naor, Mohammad R. Salavatipour, Mohit Singh: Survivable network design with degree or order constraints. STOC 2007: 651-660

Julia Chuzhoy, Joseph Naor: New hardness results for congestion minimization and machine scheduling. J. ACM 53(5): 707-721 (2006)

Yigal Bejerano, Joseph Naor, Alexander Sprintson: Efficient algorithms for shared backup allocation in networks with partial information. J. Comb. Optim. 12(1-2): 17-34 (2006)

Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, Irina Shapira: Scheduling Split Intervals. SIAM J. Comput. 36(1): 1-15 (2006)

Julia Chuzhoy, Joseph Naor: Covering Problems with Hard Capacities. SIAM J. Comput. 36(2): 498-515 (2006)

Chandra Chekuri, Sudipto Guha, Joseph Naor: The Steiner k-Cut Problem. SIAM J. Discrete Math. 20(1): 261-271 (2006)

Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor: A general approach to online network optimization problems. ACM Transactions on Algorithms 2(4): 640-660 (2006)

Yigal Bejerano, Mark A. Smith, Joseph Naor, Nicole Immorlica: Efficient location area planning for personal communication systems. IEEE/ACM Trans. Netw. 14(2): 438-450 (2006)

Niv Buchbinder, Joseph Naor: Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach. FOCS 2006: 293-304

Roee Engelberg, Jochen Könemann, Stefano Leonardi, Joseph Naor: Cut Problems in Graphs with a Budget Constraint. LATIN 2006: 435-446

Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Joseph Naor, Ariel Orda: Non-cooperative multicast and facility location games. ACM Conference on Electronic Commerce 2006: 72-81

Niv Buchbinder, Joseph Naor: Fair online load balancing. SPAA 2006: 291-298

David Amzallag, Joseph Naor, Danny Raz: Coping with Interference: From Maximum Coverage to Planning Cellular Networks. WAOA 2006: 29-42

Chandra Chekuri, Anupam Gupta, Amit Kumar, Joseph Naor, Danny Raz: Building Edge-Failure Resilient Networks. Algorithmica 43(1-2): 17-41 (2005)

Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor: Asymmetric k-center is log^* n-hard to approximate. J. ACM 52(4): 538-551 (2005)

Joseph Naor: From Balanced Graph Partitioning to Balanced Metric Labeling. ESA 2005: 9

Niv Buchbinder, Joseph Naor: Online Primal-Dual Algorithms for Covering and Packing Problems. ESA 2005: 689-701

Yigal Bejerano, Joseph Naor, Alexander Sprintson: Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information. ESA 2005: 702-713

Joseph Naor, Adi Rosén, Gabriel Scalosub: Online time-constrained scheduling in linear networks. INFOCOM 2005: 855-865

Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor: Approximating the average response time in broadcast scheduling. SODA 2005: 215-221

Julia Chuzhoy, Anupam Gupta, Joseph Naor, Amitabh Sinha: On the approximability of some network design problems. SODA 2005: 943-951

Randeep Bhatia, Nicole Immorlica, Tracy Kimbrel, Vahab S. Mirrokni, Seffi Naor, Baruch Schieber: Traffic engineering of management flows by link augmentations on confluent trees. SPAA 2005: 289-298

Joseph Naor, Roy Schwartz: Balanced metric labeling. STOC 2005: 582-591

Liane Lewin-Eytan, Joseph Naor, Ariel Orda: Admission Control in Networks with Advance Reservations. Algorithmica 40(4): 293-304 (2004)

Ari Freund, Joseph Naor: Approximating the Advertisement Placement Problem. J. Scheduling 7(5): 365-374 (2004)

Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin: A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem. SIAM J. Discrete Math. 18(3): 608-625 (2004)

Moses Charikar, Joseph Naor, Baruch Schieber: Resource optimization in QoS multicast routing of real-time multimedia. IEEE/ACM Trans. Netw. 12(2): 340-348 (2004)

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor: Machine Minimization for Scheduling Jobs with Interval Constraints. FOCS 2004: 81-90

Julia Chuzhoy, Joseph Naor: The Hardness of Metric Labeling. FOCS 2004: 108-114

Joseph Naor, Roy Schwartz: The directed circular arrangement problem. SODA 2004: 86-95

Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor: A general approach to online network optimization problems. SODA 2004: 577-586

Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor: Asymmetric k-center is log^* n-hard to approximate. STOC 2004: 21-27

Julia Chuzhoy, Joseph Naor: New hardness results for congestion minimization and machine scheduling. STOC 2004: 28-34

Amotz Bar-Noy, Ari Freund, Shimon Landa, Joseph Naor: Competitive On-Line Switching Policies. Algorithmica 36(3): 225-247 (2003)

Amotz Bar-Noy, Joseph Naor, Baruch Schieber: Pushing Dependent Data in Clients-Providers-Servers Systems. Wireless Networks 9(5): 421-430 (2003)

Chandra Chekuri, Sudipto Guha, Joseph Naor: Approximating Steiner k-Cuts. ICALP 2003: 189-199

Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor: Algorithmic Aspects of Bandwidth Trading. ICALP 2003: 751-766

Joseph Naor, Hadas Shachnai, Tami Tamir: Real-Time Scheduling with a Budget. ICALP 2003: 1123-1137

Yigal Bejerano, Nicole Immorlica, Joseph Naor, Mark Smith: Efficient location area planning for personal communication systems. MOBICOM 2003: 109-121

Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor: The online set cover problem. STOC 2003: 100-105

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor: Asymmetric k-center is log^*n-hard to Approximate. Electronic Colloquium on Computational Complexity (ECCC)(038) (2003)

Amotz Bar-Noy, Randeep Bhatia, Joseph Naor, Baruch Schieber: Minimizing Service and Operation Costs of Periodic Scheduling. Math. Oper. Res. 27(3): 518-544 (2002)

Yigal Bejerano, Israel Cidon, Joseph Naor: Efficient handoff rerouting algorithms: a competitive on-line algorithmic approach. IEEE/ACM Trans. Netw. 10(6): 749-760 (2002)

Liane Lewin-Eytan, Joseph Naor, Ariel Orda: Routing and Admission Control in Networks with Advance Reservations. APPROX 2002: 215-228

Julia Chuzhoy, Joseph Naor: Covering Problems with Hard Capacities. FOCS 2002: 481-489

Sanjeev Khanna, Joseph Naor, Danny Raz: Control Message Aggregation in Group Communication Protocols. ICALP 2002: 135-146

Juan A. Garay, Joseph Naor, Bülent Yener, Peng Zhao: On-line Admission Control and Packet Scheduling with Interleaving. INFOCOM 2002

Ari Freund, Joseph Naor: Approximating the Advertisement Placement Problem. IPCO 2002: 415-424

Chandra Chekuri, Anupam Gupta, Amit Kumar, Joseph Naor, Danny Raz: Building Edge-Failure Resilient Networks. IPCO 2002: 439-456

Amotz Bar-Noy, Ari Freund, Shimon Landa, Joseph Naor: Competitive on-line switching policies. SODA 2002: 525-534

Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, Irina Shapira: Scheduling split intervals. SODA 2002: 732-741

Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Naor, Baruch Schieber, Hadas Shachnai: Throughput maximization of real-time scheduling with batching. SODA 2002: 742-751

Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, Baruch Schieber: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5): 1069-1090 (2001)

Reuven Bar-Yehuda, Guy Even, Jon Feldman, Joseph Naor: Computing an Optimal Orientation of a Balanced Decomposition Tree for Linear Arrangement Problems. J. Graph Algorithms Appl. 5(4) (2001)

Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Approximating the Throughput of Multiple Machines in Real-Time Scheduling. SIAM J. Comput. 31(2): 331-352 (2001)

Joseph Naor, Leonid Zosin: A 2-Approximation Algorithm for the Directed Multiway Cut Problem. SIAM J. Comput. 31(2): 477-482 (2001)

Amotz Bar-Noy, Ari Freund, Joseph Naor: On-Line Load Balancing in a Hierarchical Server Topology. SIAM J. Comput. 31(2): 527-549 (2001)

Joseph Naor, Yuval Rabani: Tree packing and approximating k-cuts. SODA 2001: 26-27

Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin: Approximation algorithms for the metric labeling problem via a new linear programming formulation. SODA 2001: 109-118

Chandra Chekuri, Sanjeev Khanna, Joseph Naor: A deterministic algorithm for the cost-distance problem. SODA 2001: 232-233

Joseph Naor, Ariel Orda, Yael Petruschka: Dynamic storage allocation with known durations. Discrete Applied Mathematics 100(3): 203-213 (2000)

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Divide-and-conquer approximation algorithms via spreading metrics. J. ACM 47(4): 585-616 (2000)

Randeep Bhatia, Samir Khuller, Joseph Naor: The Loading Time Scheduling Problem. J. Algorithms 36(1): 1-33 (2000)

Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Message Multicasting in Heterogeneous Networks. SIAM J. Comput. 30(2): 347-358 (2000)

Guy Even, Joseph Naor, Leonid Zosin: An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem. SIAM J. Comput. 30(4): 1231-1252 (2000)

Guy Even, Joseph Naor, Baruch Schieber, Leonid Zosin: Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications. SIAM J. Discrete Math. 13(2): 255-267 (2000)

Yigal Bejerano, Israel Cidon, Joseph Naor: Dynamic session management for static and mobile users: a competitive on-line algorithmic approach. DIAL-M 2000: 65-74

Yigal Bejerano, Israel Cidon, Joseph Naor: Efficient Handoff Rerouting Algorithms: A Competitive On-Line Algorithmic Approach. INFOCOM 2000: 198-207

Moses Charikar, Joseph Naor, Baruch Schieber: Resource Optimization in QoS Multicast Routing of Real-Time Multimedia. INFOCOM 2000: 1518-1527

Amotz Bar-Noy, Joseph Naor, Baruch Schieber: Pushing dependent data in clients-providers-servers systems. MOBICOM 2000: 222-230

Sanjeev Khanna, Joseph Naor, F. Bruce Shepherd: Directed network design with orientation constraints. SODA 2000: 663-671

Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, Baruch Schieber: A unified approach to approximating resource allocation and scheduling. STOC 2000: 735-744

Samir Khuller, Anna Moss, Joseph Naor: The Budgeted Maximum Coverage Problem. Inf. Process. Lett. 70(1): 39-45 (1999)

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Fast Approximate Graph Partitioning Algorithms. SIAM J. Comput. 28(6): 2187-2214 (1999)

Amotz Bar-Noy, Ari Freund, Joseph Naor: On-Line Load Banancing in a Hierarchical Server Topology. ESA 1999: 77-88

Sudipto Guha, Anna Moss, Joseph Naor, Baruch Schieber: Efficient Recovery from Power Outage (Extended Abstract). STOC 1999: 574-582

Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Approximating the Throughput of Multiple Machines Under Real-Time Scheduling. STOC 1999: 622-631

Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan: Approximating Minimum Feedback Sets and Multicuts in Directed Graphs. Algorithmica 20(2): 151-174 (1998)

Yossi Azar, Rajeev Motwani, Joseph Naor: Approximating Probability Distributions Using Small Sample Spaces. Combinatorica 18(2): 151-171 (1998)

Joseph Naor, Ariel Orda, Raphael Rom: Scheduled Hot-Potato Routing. J. Graph Algorithms Appl. 2(2) (1998)

Reuven Bar-Yehuda, Dan Geiger, Joseph Naor, Ron M. Roth: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference. SIAM J. Comput. 27(4): 942-959 (1998)

Amotz Bar-Noy, Randeep Bhatia, Joseph Naor, Baruch Schieber: Minimizing Service and Operation Costs of Periodic Scheduling (Extended Abstract). SODA 1998: 11-20

Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Multicasting in Heterogeneous Networks. STOC 1998: 448-453

Joseph Naor, Ariel Orda, Yael Petruschka: Dynamic Storage Allocation with Known Durations. ESA 1997: 378-387

Joseph Naor, Baruch Schieber: Improved Approximations for Shallow-Light Spanning Trees. FOCS 1997: 536-541

Joseph Naor, Leonid Zosin: A 2-Approximation Algorithm for the Directed Multiway Cut Problem. FOCS 1997: 548-553

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Spreading Metric Based Graph Partitioning Algorithms. PPSC 1997

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Fast Approximate Graph Partitioning Algorithms. SODA 1997: 639-648

Dorit S. Hochbaum, Joseph Naor: Approximation Algorithms for Network Design Problems on Bounded Subsets. J. Algorithms 21(2): 403-414 (1996)

Michael Luby, Joseph Naor, Ariel Orda: Tight Bounds for Dynamic Storage Allocation. SIAM J. Discrete Math. 9(1): 155-166 (1996)

Yossi Azar, Joseph Naor, Raphael Rom: Routing Strategies for Fast Networks. IEEE Trans. Computers 45(2): 165-173 (1996)

Guy Even, Joseph Naor, Leonid Zosin: An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem. FOCS 1996: 310-319

Guy Even, Joseph Naor, Baruch Schieber, Leonid Zosin: Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications. ISTCS 1996: 78-88

Yossi Azar, Joseph Naor, Raphael Rom: The Competitiveness of On-Line Assignments. J. Algorithms 18(2): 221-237 (1995)

Joseph Naor, Ron M. Roth: Constructions of Permutation Arrays for Certain Scheduling Cost Measures. Random Struct. Algorithms 6(1): 39-50 (1995)

Gary L. Miller, Joseph Naor: Flow in Planar Graphs with Multiple Sources and Sinks. SIAM J. Comput. 24(5): 1002-1017 (1995)

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract). FOCS 1995: 62-71

Randeep Bhatia, Samir Khuller, Joseph Naor: The Loading Time Scheduling Problem (Extended Abstract). FOCS 1995: 72-81

Joseph Naor, Ariel Orda, Raphael Rom: Scheduled Hot-Potato Routing. INFOCOM 1995: 579-586

Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan: Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs. IPCO 1995: 14-28

Samir Khuller, Joseph Naor: Flow in Planar Graphs with Vertex Capacities. Algorithmica 11(3): 200-225 (1994)

Rajeev Motwani, Joseph Naor, Moni Naor: The Probabilistic Method Yields Deterministic Parallel Algorithms. J. Comput. Syst. Sci. 49(3): 478-516 (1994)

Dorit S. Hochbaum, Joseph Naor: Simple and Fast Algorithms for Linear and Integer Programs With Two Variables per Inequality. SIAM J. Comput. 23(6): 1179-1192 (1994)

Reuven Bar-Yehuda, Dan Geiger, Joseph Naor, Ron M. Roth: Approximation Algorithms for the Vertex Feedback Set Problem with Applications to Constraint Satisfaction and Bayesian Inference. SODA 1994: 344-354

Michael Luby, Joseph Naor, Ariel Orda: Tight Bounds for Dynamic Storage Allocation. SODA 1994: 724-732

Dorit S. Hochbaum, Nimrod Megiddo, Joseph Naor, Arie Tamir: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Math. Program. 62: 69-83 (1993)

Joseph Naor, Moni Naor: Small-Bias Probability Spaces: Efficient Constructions and Applications. SIAM J. Comput. 22(4): 838-856 (1993)

Samir Khuller, Joseph Naor, Philip N. Klein: The Lattice Structure of Flow in Planar Graphs. SIAM J. Discrete Math. 6(3): 477-490 (1993)

Amotz Bar-Noy, Rajeev Motwani, Joseph Naor: The Greedy Algorithm is Optimal for On-Line Edge Coloring. Inf. Process. Lett. 44(5): 251-253 (1992)

Amotz Bar-Noy, Rajeev Motwani, Joseph Naor: A Linear Time Approach to the Set Maxima Problem. SIAM J. Discrete Math. 5(1): 1-9 (1992)

Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, Ron M. Roth: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory 38(2): 509-516 (1992)

Yossi Azar, Joseph Naor, Raphael Rom: Routing Strategies for Fast Networks. INFOCOM 1992: 170-179

Dorit S. Hochbaum, Joseph Naor: Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality. IPCO 1992: 44-59

Yossi Azar, Joseph Naor, Raphael Rom: The Competitiveness of On-Line Assignments. SODA 1992: 203-210

Marek Chrobak, Joseph Naor: An Efficient Parallel Algorithm for Computing a Large Independent Set in Planar Graph. Algorithmica 6(6): 801-815 (1991)

Amotz Bar-Noy, Joseph Naor, Moni Naor: One-Bit Algorithms. Distributed Computing 4: 3-8 (1990)

Joseph Naor, Mark B. Novick: An Efficient Reconstruction of a Graph from its Line Graph in Parallel. J. Algorithms 11(1): 132-143 (1990)

Amotz Bar-Noy, Joseph Naor: Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments. SIAM J. Discrete Math. 3(1): 7-20 (1990)

Samir Khuller, Joseph Naor: Flow in Planar Graphs with Vertex Capacities. IPCO 1990: 367-384

Joseph Naor, Moni Naor: Small-bias Probability Spaces: Efficient Constructions and Applications. STOC 1990: 213-223

Joseph Naor, Moni Naor, Alejandro A. Schäffer: Fast Parallel Algorithms for Chordal Graphs. SIAM J. Comput. 18(2): 327-349 (1989)

Eli Gafni, Joseph Naor, Prabhakar Ragde: On Separating the Erew and Crew Pram Models. Theor. Comput. Sci. 68(3): 343-346 (1989)

Rajeev Motwani, Joseph Naor, Moni Naor: The Probabilistic Method Yields Deterministic Parallel Algorithms. FOCS 1989: 8-13

Gary L. Miller, Joseph Naor: Flow in Planar Graphs with Multiple Sources and Sinks (Extended Abstract). FOCS 1989: 112-117

Marek Chrobak, Joseph Naor: An Efficient Parallel Algorithm for Computing a Large Independent Set in a Plan Graph. SPAA 1989: 379-387

Marek Chrobak, Joseph Naor, Mark B. Novick: Using Bounded Degree Spanning Trees in the Design of Efficient Algorihtms on Claw-Free Graphs. WADS 1989: 147-162

Mauricio Karchmer, Joseph Naor: A Fast Parallel Algorithm to Color a Graph with Delta Colors. J. Algorithms 9(1): 83-91 (1988)

Joseph Naor: Computing a Perfect Matching in a Line Graph. AWOC 1988: 139-148

Amotz Bar-Noy, Joseph Naor, Moni Naor: One Bit Algorithms. PODC 1988: 66-76

Joseph Naor: A Fast Parallel Coloring of Planar Graphs with Five Colors. Inf. Process. Lett. 25(1): 51-53 (1987)

Joseph Naor, Moni Naor, Alejandro A. Schäffer: Fast Parallel Algorithms for Chordal Graphs (Extended Abstract). STOC 1987: 355-364

Shmuel Peleg, Joseph Naor, Ralph Hartley, David Avnir: Multiple Resolution Texture Analysis and Classification. IEEE Trans. Pattern Anal. Mach. Intell. 6(4): 518-523 (1984)

Joseph Naor, Shmuel Peleg: Image Compression and Filtering Using Pyramid Data Structures. IJCAI 1983: 1086-1088