# Nimrod Megiddo

## contact information

Distinguished Research Staff Member

Almaden Research Center, San Jose, CA, USA

+14089271786

Almaden Research Center, San Jose, CA, USA

+14089271786

## links

**2008**

Efficient coalition detection in traitor tracing

H Jin, J Lotspiech, N Megiddo

H Jin, J Lotspiech, N Megiddo

*Proceedings of the IFIP TC 11 23rd International Information Security Conference: Ifip 20th World Computer Congress, Ifip Sec'08, September 7-10, 2008, Milano, Italy*,*pp. 365*
Adaptive traitor tracing for large anonymous attack

Hongxia Jin, Jeff Lotspiech (Jeff), Michael Nelson, Nimrod Megiddo

Proceedings of the 8th ACM Workshop on Digital Rights Management, Alexandria, VA, USA, October 27, 2008. ACM 2008

Hongxia Jin, Jeff Lotspiech (Jeff), Michael Nelson, Nimrod Megiddo

Proceedings of the 8th ACM Workshop on Digital Rights Management, Alexandria, VA, USA, October 27, 2008. ACM 2008

Dynamic faceted search for discovery-driven analysis

Debabrata Dash, Jun Rao, Nimrod Megiddo, Anastasia Ailamaki, Guy M. Lohman

Debabrata Dash, Jun Rao, Nimrod Megiddo, Anastasia Ailamaki, Guy M. Lohman

*Proceedings of the 17th ACM Conference on Information and Knowledge Management, CIKM 2008, Napa Valley, California, USA, October 26-30, 2008*,*pp. 3--12***2007**

Consistent selectivity estimation via maximum entropy

V Markl, P J Haas, M Kutsch, N Megiddo, U Srivastava, T M Tran

V Markl, P J Haas, M Kutsch, N Megiddo, U Srivastava, T M Tran

*The VLDB Journal**16*(*1*), 55--76, Springer, 2007
The “arrangement method” for linear programming is equivalent to the phase-one method

E Hazan, N Megiddo

E Hazan, N Megiddo

*IBM Research Report RJ10414 (A0708-017), IBM*, 2007
Continuity properties of equilibrium prices and allocations in linear Fisher markets

N Megiddo, V V Vazirani

N Megiddo, V V Vazirani

*LECTURE NOTES IN COMPUTER SCIENCE**4858*, 362, Springer, 2007
Online learning with prior knowledge

E Hazan, N Megiddo

E Hazan, N Megiddo

*Lecture Notes in Computer Science**4539*, 499, Springer, 2007**2006**

Integrating a maximum-entropy cardinality estimator into DB2 UDB

M Kutsch, P J Haas, V Markl, N Megiddo, T M Tran

M Kutsch, P J Haas, V Markl, N Megiddo, T M Tran

*Lecture Notes in Computer Science**3896*, 1092, Springer, 2006
Efficient traitor tracing

Hongxia Jin, Jeff Lotspiech (Jeff), Nimrod Megiddo

International Symposium on ..., 2003 - domino.watson.ibm.com, 2006

Hongxia Jin, Jeff Lotspiech (Jeff), Nimrod Megiddo

International Symposium on ..., 2003 - domino.watson.ibm.com, 2006

MAXENT: consistent cardinality estimation in action

Volker Markl, MARCEL KUTSCH, Tam Minh Tran, Peter J Haas, Nimrod Megiddo

SIGMOD 2006 - Proceedings of the 2006 ACM SIGMOD international conference on Management of data

Volker Markl, MARCEL KUTSCH, Tam Minh Tran, Peter J Haas, Nimrod Megiddo

SIGMOD 2006 - Proceedings of the 2006 ACM SIGMOD international conference on Management of data

Combining expert advice in reactive environments

Daniela Pucci de Farias, Nimrod Megiddo

Journal of the Association for Computing Machinery (J. ACM) 53 (2006) 762-799.

Daniela Pucci de Farias, Nimrod Megiddo

Journal of the Association for Computing Machinery (J. ACM) 53 (2006) 762-799.

ISOMER: Consistent histogram construction using query feedback

Utkarsh Srivastava, Peter J Haas, Volker Markl, Nimrod Megiddo, MARCEL KUTSCH, Tam Minh Tran

ICDE 2006 - The 22nd IEEE International Conference on Data Engineering, 2006

Utkarsh Srivastava, Peter J Haas, Volker Markl, Nimrod Megiddo, MARCEL KUTSCH, Tam Minh Tran

ICDE 2006 - The 22nd IEEE International Conference on Data Engineering, 2006

**2005**

Exploration-exploitation tradeoffs for experts algorithms in reactive environments

D Farias de, N Megiddo

D Farias de, N Megiddo

*Advances in neural information processing systems**17*, 409--416, Citeseer, 2005
Algorithmic Applications in Management

Nimrod Megiddo, Yingfeng Xu, Binhai Zhu

AAIM 2005 - First International Conference on Algorithmic Applications in Management, Xian, China, 2005 (Edited)

Nimrod Megiddo, Yingfeng Xu, Binhai Zhu

AAIM 2005 - First International Conference on Algorithmic Applications in Management, Xian, China, 2005 (Edited)

Consistently estimating the selectivity of conjuncts of predicates

Volker Markl, Nimrod Megiddo, MARCEL KUTSCH, Tam Minh Tran, Peter J Haas, Utkarsh Srivastava

VLDB 2005 - Proceedings of the 31st international conference on Very Large Data Bases, 2005

Volker Markl, Nimrod Megiddo, MARCEL KUTSCH, Tam Minh Tran, Peter J Haas, Utkarsh Srivastava

VLDB 2005 - Proceedings of the 31st international conference on Very Large Data Bases, 2005

**2004**

Linear Programming

Martin E. Dyer, Nimrod Megiddo, Emo Welzl

CRC Handbook of Discrete and Computational Geometry, Second Edition, 2004

Martin E. Dyer, Nimrod Megiddo, Emo Welzl

CRC Handbook of Discrete and Computational Geometry, Second Edition, 2004

Outperforming LRU with an adaptive replacement cache algorithm

Nimrod Megiddo, Dharmendra S Modha

Nimrod Megiddo, Dharmendra S Modha

*Computer**37*(*4*), 58--65, IEEE, 2004**2003**

System and methodology for video conferencing and internet chatting in a cocktail party style

N Megiddo

US Patent 6,559,863, 2003 - Google Patents, Google Patents

US Patent 6,559,863

N Megiddo

US Patent 6,559,863, 2003 - Google Patents, Google Patents

US Patent 6,559,863

A Simple Adaptive Cache Algorithm Outperforms LRU

N Megiddo, D S Modha

N Megiddo, D S Modha

*IBM Research Report, Computer Science*, 2003
How to combine expert (or novice) advice when actions impact the environment

Daniela Pucci de Farias, Nimrod Megiddo

NIPS 2003 - Neural Information Processing Systems 16

Daniela Pucci de Farias, Nimrod Megiddo

NIPS 2003 - Neural Information Processing Systems 16

ARC: A self-tuning, low overhead replacement cache

Nimrod Megiddo, Dharmendra S Modha

Nimrod Megiddo, Dharmendra S Modha

*Proceedings of the 2nd USENIX Conference on File and Storage Technologies*,*pp. 115--130*, 2003**2002**

Automating physical database design in a parallel database

Jun Rao, Chun Zhang, Nimrod Megiddo, Guy M. Lohman

Jun Rao, Chun Zhang, Nimrod Megiddo, Guy M. Lohman

*Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, Wisconsin, June 3-6, 2002*,*pp. 558--569*
Attribute Classification Using Feature Analysis

Felix Naumann, Ching

Tien Ho (Howard), Xuqing Tian, Laura Haas, Nimrod Megiddo - ICDE 2002 - 18th International Conference on Data Engineering, 2002.

Felix Naumann, Ching

Tien Ho (Howard), Xuqing Tian, Laura Haas, Nimrod Megiddo - ICDE 2002 - 18th International Conference on Data Engineering, 2002.

**2001**

Restructuring of executable computer code and large data sets

N Megiddo, B Mendelson

US Patent App. 09/902,595, 2001 - Google Patents, Google Patents

US Patent App. 09/902,595

N Megiddo, B Mendelson

US Patent App. 09/902,595, 2001 - Google Patents, Google Patents

US Patent App. 09/902,595

System and method for discovering predictive association rules

N Megiddo, R Srikant

US Patent 6,182,070, 2001 - Google Patents, Google Patents

US Patent 6,182,070

N Megiddo, R Srikant

US Patent 6,182,070, 2001 - Google Patents, Google Patents

US Patent 6,182,070

Improved algorithms and analysis for secretary problems and generalizations

Miklos Ajtai, Nimrod Megiddo, Orli Waarts

SIAM Journal on Discrete Mathematics 14 (2001) 1-27.

Miklos Ajtai, Nimrod Megiddo, Orli Waarts

SIAM Journal on Discrete Mathematics 14 (2001) 1-27.

An improved predictive accuracy bound for averaging classifiers

John Langford, Matthias Seeger, Nimrod Megiddo

ICML 2001 - Proceedings of the 18th International Conference on Machine Learning, 2001

John Langford, Matthias Seeger, Nimrod Megiddo

ICML 2001 - Proceedings of the 18th International Conference on Machine Learning, 2001

**2000**

Method of, system for, and computer program product for performing weighted loop fusion by an optimizing compiler

N Megiddo, V Sarkar

US Patent 6,058,266, 2000 - Google Patents, Google Patents

US Patent 6,058,266

N Megiddo, V Sarkar

US Patent 6,058,266, 2000 - Google Patents, Google Patents

US Patent 6,058,266

On structured Markov decision processes in continuous state space

Nimrod Megiddo

Research Report RJ 10264, IBM Almaden Research Center, San Jose, CA, 2000.

Nimrod Megiddo

Research Report RJ 10264, IBM Almaden Research Center, San Jose, CA, 2000.

A sublinear parallel algorithm for stable matching

T Feder, N Megiddo, S A Plotkin

T Feder, N Megiddo, S A Plotkin

*Theoretical Computer Science**233*(*1-2*), 297--308, Elsevier, 2000
An analytical model for loop tiling and its solution

V Sarkar, N Megiddo

V Sarkar, N Megiddo

*2000 IEEE International Symposium on Performance Analysis of Systems and Software, 2000*,*pp. 146--153*
Interval hash tree: An efficient index structure for searching object queries in large image databases,

Tanveer Syeda

Mahmood, Prabhakar Raghavan, Nimrod Megiddo - CBAIVL 2000 - IEEE Workshop on Content-Based Access of Image and Video Libraries

Tanveer Syeda

Mahmood, Prabhakar Raghavan, Nimrod Megiddo - CBAIVL 2000 - IEEE Workshop on Content-Based Access of Image and Video Libraries

**1999**

A fast indexing method for multidimensional nearest neighbor search

John Shepherd, Xiaoming Zhu, Nimrod Megiddo

SPIE 1999 - Conference on Storage and Retrieval for Image and Video, 1999

John Shepherd, Xiaoming Zhu, Nimrod Megiddo

SPIE 1999 - Conference on Storage and Retrieval for Image and Video, 1999

**1998**

Fast query search in large dimension database

J L Hafner, N Megiddo, E Upfal

US Patent 5,848,404, 1998 - Google Patents, Google Patents

US Patent 5,848,404

J L Hafner, N Megiddo, E Upfal

US Patent 5,848,404, 1998 - Google Patents, Google Patents

US Patent 5,848,404

Using fast matrix multiplication to find basic solutions

P A Beling, N Megiddo

P A Beling, N Megiddo

*Theoretical Computer Science**205*(*1-2*), 307--316, Elsevier, 1998
A conjugate direction method for approximating the analytic center of a polytope

Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno

Journal of Inequalities and Applications 2 (1998) 181-194.

Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno

Journal of Inequalities and Applications 2 (1998) 181-194.

A modified layered-step interior-point algorithm for linear programming

Nimrod Megiddo, Shinji Mizuno, Takashi Tsuchiya

Mathematical Programming 82 (1998) 339-355.

Nimrod Megiddo, Shinji Mizuno, Takashi Tsuchiya

Mathematical Programming 82 (1998) 339-355.

Discovering predictive association rules

Nimrod Megiddo, Ramakrishnan Srikant

KDD 1998 - Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, 1998

Nimrod Megiddo, Ramakrishnan Srikant

KDD 1998 - Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, 1998

Discovery-driven exploration of OLAP data cubes

Sunita Sarawagi, Rakesh Agrawal, Nimrod Megiddo

EDBT 1998 - Sixth International Conference on Extending Database Technology, 1998

Sunita Sarawagi, Rakesh Agrawal, Nimrod Megiddo

EDBT 1998 - Sixth International Conference on Extending Database Technology, 1998

**1997**

Techniques for speeding up range-max queries in OLAP data cubes

CT Ho, R Agrawal, N Megiddo, JJ Tsay

CT Ho, R Agrawal, N Megiddo, JJ Tsay

*IBM Research Report*, Citeseer, 1997
Efficient nearest neighbor indexing based on a collection of space-filling curves

N Megiddo, U Shaft

N Megiddo, U Shaft

*Research Report, IBM Almaden Research Center, San Jose, California, USA*, 1997
Range queries in OLAP data cubes

Ching

Tien Ho (Howard), Rakesh Agrawal, Nimrod Megiddo, Ramakrishnan Srikant - Research Report RJ 10070, IBM Almaden Research Center, San Jose, CA 1997.

Ching

Tien Ho (Howard), Rakesh Agrawal, Nimrod Megiddo, Ramakrishnan Srikant - Research Report RJ 10070, IBM Almaden Research Center, San Jose, CA 1997.

Efficient nearest neighbor indexing based on a collection of space filling curves

Nimrod Megiddo, Uri Shaft

Research Report RJ 10093, IBM Almaden Research Center, San Jose, CA, 1997

Nimrod Megiddo, Uri Shaft

Research Report RJ 10093, IBM Almaden Research Center, San Jose, CA, 1997

Fast algorithms for range-max queries in OLAP data cubes

Ching

Tien Ho (Howard), Nimrod Megiddo, J. J. Tsay - Research Report RJ 10071, IBM Almaden Research Center, San Jose, CA 1997.

Ching

Tien Ho (Howard), Nimrod Megiddo, J. J. Tsay - Research Report RJ 10071, IBM Almaden Research Center, San Jose, CA 1997.

Linear programming in low dimensions

Martin E. Dyer, Nimrod Megiddo

CRC Handbook of Discrete and Computational Geometry, 1997

Martin E. Dyer, Nimrod Megiddo

CRC Handbook of Discrete and Computational Geometry, 1997

Optimal weighted loop fusion for parallel programs

Nimrod Megiddo, Vivek Sarkar

SPAA 1997 - Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, 1997

Nimrod Megiddo, Vivek Sarkar

SPAA 1997 - Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, 1997

Range queries in OLAP data cubes

Ching

Tien Ho (Howard), Rakesh Agrawal, Nimrod Megiddo, Ramakrishnan Srikant - SIGMOD 1997 - Proceedings of the 1997 ACMSIGMOD International Conference on Management of Data

Ching

Tien Ho (Howard), Rakesh Agrawal, Nimrod Megiddo, Ramakrishnan Srikant - SIGMOD 1997 - Proceedings of the 1997 ACMSIGMOD International Conference on Management of Data

**1996**

Simulation and Optimization of HDA Testing

Susan Juge, Nimrod Megiddo, Erika Schraner

Research Report RJ 10037, IBM Almaden Research Center, San Jose, CA 1996.

Susan Juge, Nimrod Megiddo, Erika Schraner

Research Report RJ 10037, IBM Almaden Research Center, San Jose, CA 1996.

Finding a line of sight through boxes in d-space in linear time

Nimrod Megiddo

Research Report RJ 10018, IBM Almaden Research Center, San Jose, California, 1996.

Nimrod Megiddo

Research Report RJ 10018, IBM Almaden Research Center, San Jose, California, 1996.

Segmenting and representing background in color images

Q Huang, B Dom, N Megiddo, W Niblack

Q Huang, B Dom, N Megiddo, W Niblack

*Proceedings of ICPR*, 1996
Color image background segmentation and representation

Qian Huang, Nimrod Megiddo

ICIP 1996 - Proceedings of the 1996 IEEE International Conference on Image Processing

Qian Huang, Nimrod Megiddo

ICIP 1996 - Proceedings of the 1996 IEEE International Conference on Image Processing

A linear programming instance with many crossover events

S Mizuno, N Megiddo, T Tsuchiya

S Mizuno, N Megiddo, T Tsuchiya

*Journal of Complexity**12*(*4*), 474--479, Elsevier, 1996
A deterministic poly(log log n)-time n-processor algorithm for linear programming in fixed dimension

Miklos Ajtai, Nimrod Megiddo

SIAM Journal on Computing 25 (1996) 1171-1195.

Miklos Ajtai, Nimrod Megiddo

SIAM Journal on Computing 25 (1996) 1171-1195.

On the geometric separability of boolean functions

Tibor Hegedus, Nimrod Megiddo

Discrete Applied Mathematics 66 (1996) 205-218.

Tibor Hegedus, Nimrod Megiddo

Discrete Applied Mathematics 66 (1996) 205-218.

Finding mixed strategies with small supports in extensive form games

Daphne Koller, Nimrod Megiddo

International Journal of Game Theory 25 (1996) 73-92.

Daphne Koller, Nimrod Megiddo

International Journal of Game Theory 25 (1996) 73-92.

Efficient computation of equilibria for extensive two-person games

Daphne Koller, Nimrod Megiddo, Bernhard von Stengel

Games and Economic Behavior 14 (1996) 220-246.

Daphne Koller, Nimrod Megiddo, Bernhard von Stengel

Games and Economic Behavior 14 (1996) 220-246.

**1995**

Improved Algorithms and Analysis for Secretary Problems and Generalizations

Miklos Ajtai, Nimrod Megiddo, Orli Waarts

FOCS 1995 - 36th Annual Symposium on Foundations of Computer Science, 1995

Miklos Ajtai, Nimrod Megiddo, Orli Waarts

FOCS 1995 - 36th Annual Symposium on Foundations of Computer Science, 1995

**1994**

On probabilistic machines, bounded rationality, and average-case complexity

Nimrod Megiddo

in: Essays in Game Theory Honor of Michael Maschler, Springer-Verlag, 1994

Nimrod Megiddo

in: Essays in Game Theory Honor of Michael Maschler, Springer-Verlag, 1994

Decomposition in Interior-Point Methods

Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno, Susumu Shindoh

Optimization - Modeling and Algorithms, The Institute of Statistical Mathematics, Tokyo, Japan, March 1994

Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno, Susumu Shindoh

Optimization - Modeling and Algorithms, The Institute of Statistical Mathematics, Tokyo, Japan, March 1994

Constructing Small Sample Spaces Satisfying Given Constants

Daphne Koller, Nimrod Megiddo

SIAM Journal on Discrete Mathematics 7 (1994) 260-274.

Daphne Koller, Nimrod Megiddo

SIAM Journal on Discrete Mathematics 7 (1994) 260-274.

Algorithms and complexity analysis of some flow problems

Edith Cohen, Nimrod Megiddo

Algorithmica 11 (1994) 320-340.

Edith Cohen, Nimrod Megiddo

Algorithmica 11 (1994) 320-340.

Improved algorithms for linear inequalities with two variables per inequality

Edith Cohen, Nimrod Megiddo

SIAM Journal on Computing 23 (1994) 1313-1350

Edith Cohen, Nimrod Megiddo

SIAM Journal on Computing 23 (1994) 1313-1350

New algorithms for generalized network flows

Edith Cohen, Nimrod Megiddo

Mathematical Programming 64 (1994) 325-336.

Edith Cohen, Nimrod Megiddo

Mathematical Programming 64 (1994) 325-336.

Parallel linear programming in fixed dimension almost surely in constant time

Noga Alon, Nimrod Megiddo

Journal of the Association for Computing Machinery (J. ACM) 41 (1994) 422-434.

Noga Alon, Nimrod Megiddo

Journal of the Association for Computing Machinery (J. ACM) 41 (1994) 422-434.

Fast algorithms for finding randomized strategies in game trees

Daphne Koller, Nimrod Megiddo, Bernhard von Stengel

STOC 1994 - Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994

Daphne Koller, Nimrod Megiddo, Bernhard von Stengel

STOC 1994 - Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994

**1993**

Horizontal and vertical decomposition in interior point methods for linear programs

M Kojima, N Megiddo, S Mizuno, S Shindoh

M Kojima, N Megiddo, S Mizuno, S Shindoh

*Dept. of Mathematical and Computing Sciences Technical report, Tokyo Institute of Technology*, Citeseer, 1993
A general NP-completeness Theorem

N Megiddo

N Megiddo

*From Topology to Computation, Proceedings of the Smalefest*,*pp. 432--442*, 1993
The minimum reservation rate problem in digital audio/video systems

D P A N Megiddo, M Naor

D P A N Megiddo, M Naor

*contract**14*(*91-C*), 0026, Citeseer, 1993
Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs

E Cohen, N Megiddo

E Cohen, N Megiddo

*Journal of the ACM (JACM)**40*(*4*), 791--830, ACM New York, NY, USA, 1993
Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs

Edith Cohen, Nimrod Megiddo

Journal of the Association for Computing Machinery (J. ACM) 40 (1993) 791-832.

Edith Cohen, Nimrod Megiddo

Journal of the Association for Computing Machinery (J. ACM) 40 (1993) 791-832.

Maximizing concave functions in fixed dimension

Edith Cohen, Nimrod Megiddo

Complexity in Numerical Optimization, 1993

Edith Cohen, Nimrod Megiddo

Complexity in Numerical Optimization, 1993

Linear time algorithms for some separable quadratic programming problems

Nimrod Megiddo, Arie Tamir

Operations Research Letters 13 (1993) 203-211.

Nimrod Megiddo, Arie Tamir

Operations Research Letters 13 (1993) 203-211.

A general framework of continuation methods for complementarity problems

Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno

Mathematics of Operations Research 18 (1993) 945-963.

Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno

Mathematics of Operations Research 18 (1993) 945-963.

Constructing small sample spaces satisfying given constraints

Daphne Koller, Nimrod Megiddo

STOC 1993 - Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993

Daphne Koller, Nimrod Megiddo

STOC 1993 - Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993

Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

Dorit S. Hochbaum, Nimrod Megiddo, Joseph Naor, Arie Tamir

Mathematical Programming 62 (1993) 69-84.

Dorit S. Hochbaum, Nimrod Megiddo, Joseph Naor, Arie Tamir

Mathematical Programming 62 (1993) 69-84.

A primal—dual infeasible-interior-point algorithm for linear programming

M Kojima, N Megiddo, S Mizuno

M Kojima, N Megiddo, S Mizuno

*Mathematical Programming**61*(*1*), 263--280, Springer, 1993
Theoretical convergence of large-step primal-dual interior point algorithms for linear programming

Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno

Mathematical Programming 59 (1993) 1-22.

Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno

Mathematical Programming 59 (1993) 1-22.

**1992**

A Lagrangian Relaxation Method for Approximating the Analytic Center of a Polytope

M Kojima, N Megiddo, S Mizuno

M Kojima, N Megiddo, S Mizuno

*Technical Report, IBM Almaden Research*, Citeseer, 1992
Linear Programming

Nimrod Megiddo

Encyclopedia of Microcomputers Vol. 10, Marcel Dekker, Inc., New York, 1992, pp. 205210.

Nimrod Megiddo

Encyclopedia of Microcomputers Vol. 10, Marcel Dekker, Inc., New York, 1992, pp. 205210.

New algorithms for generalized network flows

Edith Cohen, Nimrod Megiddo

ISTCS 1992 - The 1992 Israel Symposium on the Theory of Computing and Systems, Lecture Notes in Computer Science, Vol. 601

Edith Cohen, Nimrod Megiddo

ISTCS 1992 - The 1992 Israel Symposium on the Theory of Computing and Systems, Lecture Notes in Computer Science, Vol. 601

A deterministic poly (log log n)-time n-processor algorithm for linear programming in fixed …

Miklos Ajtai, Nimrod Megiddo

STOC 1992 - Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Miklos Ajtai, Nimrod Megiddo

STOC 1992 - Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

An interior point potential reduction algorithm for the linear complementarity problem

Masakazu Kojima, Nimrod Megiddo, Yinyu Ye

Mathematical programming 54 (1992) 267-279.

Masakazu Kojima, Nimrod Megiddo, Yinyu Ye

Mathematical programming 54 (1992) 267-279.

On the complexity of two-person zero-sum games in extensive Form

Daphne Koller, Nimrod Megiddo

Games and Economic Behavior 4 (1992) 528-552.

Daphne Koller, Nimrod Megiddo

Games and Economic Behavior 4 (1992) 528-552.

**1991**

A primal-dual infeasible-interior-point algorithm for linear programming, Research Report RJ 8500, IBM Almaden Research Center, San Jose

M Kojima, N Megiddo, S Mizuno

CA, CA, 1991

M Kojima, N Megiddo, S Mizuno

CA, CA, 1991

The relation between the path of centers and Smale's regularization of the linear programming problem.

M Kojima, N Megiddo

M Kojima, N Megiddo

*LINEAR ALGEBRA APPLIC.**152*, 135--139, Citeseer, 1991
The relation between the path of centers and Smales regularization of the linear programming problem

Masakazu Kojima, Nimrod Megiddo

Linear Algebra and Its Applications 152 (1991) 135-139.

Masakazu Kojima, Nimrod Megiddo

Linear Algebra and Its Applications 152 (1991) 135-139.

Algorithms and complexity analysis for some flow problems

Edith Cohen, Nimrod Megiddo

SODA 1991 - Second Annual ACM/SIAM Symposium on Discrete Algorithms, 1991.

Edith Cohen, Nimrod Megiddo

SODA 1991 - Second Annual ACM/SIAM Symposium on Discrete Algorithms, 1991.

Exact computation of optimal inventory policies over an unbounded horizon

Refael Hassin, Nimrod Megiddo

Mathematics of Operations Research 16 (1991) 534-546

Refael Hassin, Nimrod Megiddo

Mathematics of Operations Research 16 (1991) 534-546

Recognizing properties of periodic graphs

Edith Cohen, Nimrod Megiddo

Applied Geometry and Discrete Mathematics -The Victor Klee Festschrift, American Mathematical Society, 1991

Edith Cohen, Nimrod Megiddo

Applied Geometry and Discrete Mathematics -The Victor Klee Festschrift, American Mathematical Society, 1991

Improved algorithms for linear inequalities with two variables per inequality

Edith Cohen, Nimrod Megiddo

STOC 1991 - Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Edith Cohen, Nimrod Megiddo

STOC 1991 - Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Approximation algorithms for hitting objects with straight lines

Refael Hassin, Nimrod Megiddo

Discrete Applied Mathematics 30 (1991) 29-42.

Refael Hassin, Nimrod Megiddo

Discrete Applied Mathematics 30 (1991) 29-42.

A unified approach to interior point algorithms for linear complementarity problems

Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, Akiko Yoshise

Springer-Verlag, 1991

Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, Akiko Yoshise

Springer-Verlag, 1991

A note on total functions, existence theorems, and computational complexity

Nimrod Megiddo, Christos H. Papadimitriou

Theoretical Computer Science 81 (1991) 317-324.

Nimrod Megiddo, Christos H. Papadimitriou

Theoretical Computer Science 81 (1991) 317-324.

Homotopy continuation methods for nonlinear complementarity problems

Masakazu Kojima, Nimrod Megiddo, Toshihito Noma

Mathematics of Operations Research 16 (1991) 754-774.

Masakazu Kojima, Nimrod Megiddo, Toshihito Noma

Mathematics of Operations Research 16 (1991) 754-774.

**1990**

Recognizing Properties of Periodic Graphs. Research Report RJ 7246 (68013), IBM Almaden Research Center

E Cohen, N Megiddo

October, October, 1990

E Cohen, N Megiddo

October, October, 1990

Theoretical convergence of large $\{$step primal $\{$dual interior point algorithms for linear programs. RJ 7872, IBM Almaden Research Center, San Jose, California

M Kojima, N Megiddo, S Mizuno

M Kojima, N Megiddo, S Mizuno

*Mathematical Programming*, 1990
Parallel linear programming in fixed dimension almost surely in constant time

Noga Alon, Nimrod Megiddo

FOCS 1990 - 31th Annual IEEE Symposium on Foundations of Computer Science, 1990

Noga Alon, Nimrod Megiddo

FOCS 1990 - 31th Annual IEEE Symposium on Foundations of Computer Science, 1990

A unified approach to interior point algorithms for linear complementarity problems: A summary

M Kojima, N Megiddo, T Noma, A Yoshise

M Kojima, N Megiddo, T Noma, A Yoshise

*Research ReportRJ7493 (70008), IBM Almaden Research Center*, 95120--6099, Citeseer, 1990
Linear programming with two variables per inequality in poly log time

George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran

SIAM Journal on Computing 19 (1990) 1000-1010.

George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran

SIAM Journal on Computing 19 (1990) 1000-1010.

On solving the linear programming problem approximately

Nimrod Megiddo

Contemporary Mathematics 114 (1990) 35-50.

Nimrod Megiddo

Contemporary Mathematics 114 (1990) 35-50.

A logic for reasoning about probabilities

R Fagin, J Y Halpern, N Megiddo

R Fagin, J Y Halpern, N Megiddo

*Information and computation**87*(*1-2*), 78--128, Elsevier, 1990
On the complexity of some geometric problems in unbounded dimension

Nimrod Megiddo

Journal of Symbolic Computation 10 (1990) 327-324.

Nimrod Megiddo

Journal of Symbolic Computation 10 (1990) 327-324.

A logic for reasoning about probabilities.

R Fagin, J Y Halpern, N Megiddo

R Fagin, J Y Halpern, N Megiddo

*INF. COMPUT.**87*(*1*), 78--128, Citeseer, 1990**1989**

On orientations and shortest paths

Refael Hassin, Nimrod Megiddo

Linear Algebra and Its Applications 114/115 (1989) 589-602.

Refael Hassin, Nimrod Megiddo

Linear Algebra and Its Applications 114/115 (1989) 589-602.

Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs

Edith Cohen, Nimrod Megiddo

STOC 1989 - Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Edith Cohen, Nimrod Megiddo

STOC 1989 - Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Progress in Mathematical Programming: Interior-point and Related Methods

Nimrod Megiddo

Springer-Verlag, 1989

Nimrod Megiddo

Springer-Verlag, 1989

Boundary behavior of interior point algorithms in linear programming

Nimrod Megiddo, Michael Shub

Mathematics of Operations Research 14 (1989) 97-146.

Nimrod Megiddo, Michael Shub

Mathematics of Operations Research 14 (1989) 97-146.

Pathways to the optimal set in linear programming

Nimrod Megiddo

Progress in Mathematical Programming: Interior Point and Related Methods, 1989

Nimrod Megiddo

Progress in Mathematical Programming: Interior Point and Related Methods, 1989

**1988**

A Note on Complexity of P-Matrix L с P and Computing an Equilibrium

N Megiddo

N Megiddo

*IBM Almad{\'e}n Research Center*, 1988
Switching from a primal $\{$dual Newton algorithm to a primal $\{$dual (interior) simplex $\{$algorithm. RJ 6327 (61996)

N Megiddo

N Megiddo

*IBM Almaden Research Center, San Jose, California*, 1988
On finding primal $\{$and dual $\{$optimal bases. RJ 6328 (61997)

N Megiddo

N Megiddo

*IBM Almaden Research Center, San Jose, California*, 1988
On the epsilon-perturbation method for avoiding degeneracy

Nimrod Megiddo, Ramaswami Chandrasekaran

Research Report RJ 6330, IBM Almaden Research Center, San Jose, California, 1988.

Nimrod Megiddo, Ramaswami Chandrasekaran

Research Report RJ 6330, IBM Almaden Research Center, San Jose, California, 1988.

On finding additive, superadditive and subadditive set-functions subject to linear inequalities

Nimrod Megiddo

Research Report RJ 6329, IBM Almaden Research Center, San Jose, California, 1988

Nimrod Megiddo

Research Report RJ 6329, IBM Almaden Research Center, San Jose, California, 1988

Switching from a primal-dual Newton algorithm to a primal-dual (interior) simplex algorithm

Nimrod Megiddo

Research Report RJ 6327, IBM Almaden Research Center, San Jose, California, 1988

Nimrod Megiddo

Research Report RJ 6327, IBM Almaden Research Center, San Jose, California, 1988

A note on Karmarkars projective transformation

Nimrod Megiddo

IBM Almaden Research Center, San Jose, California, , December 1988

Nimrod Megiddo

IBM Almaden Research Center, San Jose, California, , December 1988

On the epsilon-perturbation method for avoiding degeneracy

N Megiddo, R Chandrasekaran

N Megiddo, R Chandrasekaran

*IBM Almaden Research*, 8--305, Citeseer, 1988
On finding a minimum dominating set in a tournament

Nimrod Megiddo, Uzi Vishkin

Theoretical Computer Science 61 (1988) 307-316.

Nimrod Megiddo, Uzi Vishkin

Theoretical Computer Science 61 (1988) 307-316.

A note on the complexity of P-matrix LCP and computing an equilibrium

Nimrod Megiddo

Research Report RJ6439, IBM Almaden Research Center, San Jose, CA, 1988

Nimrod Megiddo

Research Report RJ6439, IBM Almaden Research Center, San Jose, CA, 1988

On the complexity of polyhedral separability

Nimrod Megiddo

Discrete and Computational Geometry 3 (1988) 325-327.

Nimrod Megiddo

Discrete and Computational Geometry 3 (1988) 325-327.

The complexity of searching a graph

Nimrod Megiddo, S. Louis Hakimi, Michael R. Garey, David S. Johnson, Christos H. Papadimitriou

Journal of the Association for Computing Machinery (J. ACM) 35 (1988) 18-44.

Nimrod Megiddo, S. Louis Hakimi, Michael R. Garey, David S. Johnson, Christos H. Papadimitriou

Journal of the Association for Computing Machinery (J. ACM) 35 (1988) 18-44.

**1987**

Turing Machines Play the Finitely Repeated Prisoners' Dilemma," IBM Almaden Research Center, San Jose California

N Megiddo, R Widgerson

Technical Report, 1987

N Megiddo, R Widgerson

Technical Report, 1987

On the complexity of solving the generalized set packing problem approximately

Nimrod Megiddo

Research Report RJ 5898, IBM Almaden Research Center, San Jose, California, 1987

Nimrod Megiddo

Research Report RJ 5898, IBM Almaden Research Center, San Jose, California, 1987

On the complexity of linear programming

Nimrod Megiddo

Advances in Economic Theory: Fifth world congress, T. Bewley, ed., 1987

Nimrod Megiddo

Advances in Economic Theory: Fifth world congress, T. Bewley, ed., 1987

**1986**

Remarks on Bounded Rationality," Research Report RJ5270, IBM Almaden Research Center, San Jose, California.(1989):$\backslash$ On Computable Beliefs of Rational Machines,"

N Megiddo

N Megiddo

*Games and Economic Behavior**1*, 144--69, 1986
Linear programming with two variables per inequality in poly log time

George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran

STOC 1986 - The 18th Annual ACM Symposium on Theory of Computing

George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran

STOC 1986 - The 18th Annual ACM Symposium on Theory of Computing

Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm

N Megiddo

N Megiddo

*Mathematical Programming**35*(*2*), 140--172, Springer, 1986
On the expected number of linear complementarity cones intersected by random and semi-random rays

N Megiddo

N Megiddo

*Mathematical Programming**35*(*2*), 225--235, Springer, 1986
Introduction: New approaches to linear programming

N Megiddo

N Megiddo

*Algorithmica**1*(*1*), 387--394, Springer, 1986
A note on degeneracy in linear programming

N Megiddo

N Megiddo

*Mathematical Programming**35*(*3*), 365--367, Springer, 1986
A randomizing O(n log n) algorithm for the weighted Euclidean 1-center problem

Nimrod Megiddo, Eitan Zemel

Journal of Algorithms 7 (1986) 358-368.

Nimrod Megiddo, Eitan Zemel

Journal of Algorithms 7 (1986) 358-368.

On play by means of computing machines

Nimrod Megiddo, Avi Wigderson

TARK 1986 - Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning about Knowledge

Nimrod Megiddo, Avi Wigderson

TARK 1986 - Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning about Knowledge

**1985**

A note on sensitivity analysis in algebraic algorithms

Nimrod Megiddo

Research Report RJ 4958, IBM Almaden Research Center, San Jose, California, 1985.

Nimrod Megiddo

Research Report RJ 4958, IBM Almaden Research Center, San Jose, California, 1985.

Optimal precision in the presence of uncertainty

Joseph Y. Halpern, Nimrod Megiddo, Ashfaq A. Munshi

Journal of Complexity 49 (1985) 271-275.

Joseph Y. Halpern, Nimrod Megiddo, Ashfaq A. Munshi

Journal of Complexity 49 (1985) 271-275.

A note on the generality of the self-dual algorithm with various starting points

Nimrod Megiddo

Methods of Operations Research 48 (1985) 871-895.

Nimrod Megiddo

Methods of Operations Research 48 (1985) 871-895.

An optimal algorithm for finding all the steps of a monotone step-function

Refael Hassin, Nimrod Megiddo

Journal of Algorithms 6 (1985) 265-274.

Refael Hassin, Nimrod Megiddo

Journal of Algorithms 6 (1985) 265-274.

A two-resource allocation problem solvable in linear time

Nimrod Megiddo, Tetsuo Ichimori

Mathematics of Operations Research 10 (1985) 7-16.

Nimrod Megiddo, Tetsuo Ichimori

Mathematics of Operations Research 10 (1985) 7-16.

Optimal precision in the presence of uncertainty

Joseph Y. Halpern, Nimrod Megiddo, Ashfaq A. Munshi

STOC 1985 - Proceedings of the seventeenth annual ACM symposium on Theory of Computing

Joseph Y. Halpern, Nimrod Megiddo, Ashfaq A. Munshi

STOC 1985 - Proceedings of the seventeenth annual ACM symposium on Theory of Computing

A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension

Ilan Adler, Nimrod Megiddo

Journal of the Association for Computing Machinery (J. ACM) 32 (1985) 871-895.

Ilan Adler, Nimrod Megiddo

Journal of the Association for Computing Machinery (J. ACM) 32 (1985) 871-895.

**1984**

A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension

Ilan Adler, Nimrod Megiddo

STOC 1984 - Proceedings of the sixteenth annual ACM symposium on Theory of Computing

Ilan Adler, Nimrod Megiddo

STOC 1984 - Proceedings of the sixteenth annual ACM symposium on Theory of Computing

New results on the behavior of simplex algorithms

Ilan Adler, Nimrod Megiddo, Michael J. Todd

Bulletin of the American Mathematical Society 11 (1984) 378-382.

Ilan Adler, Nimrod Megiddo, Michael J. Todd

Bulletin of the American Mathematical Society 11 (1984) 378-382.

Linear programming in linear time when the dimension is fixed

Nimrod Megiddo

Journal of the Association for Computing Machinery (J.ACM) 31 (1984) 114-127.

Nimrod Megiddo

Journal of the Association for Computing Machinery (J.ACM) 31 (1984) 114-127.

On the complexity of some common geometric location problems

Nimrod Megiddo, Kenneth J. Supowit

SIAM Journal on Computing 13 (1984) 182-196.

Nimrod Megiddo, Kenneth J. Supowit

SIAM Journal on Computing 13 (1984) 182-196.

**1983**

Linear-time algorithms for linear programming in R^3 and related problems

Nimrod Megiddo

SIAM Journal on Computing 12 (1983) 759-776.

Nimrod Megiddo

SIAM Journal on Computing 12 (1983) 759-776.

Towards a genuinely polynomial algorithm for linear programming

Nimrod Megiddo

SIAM Journal on Computing 12 (1983) 347-353.

Nimrod Megiddo

SIAM Journal on Computing 12 (1983) 347-353.

Finding least-distances lines.

Nimrod Megiddo, Arie Tamir

SIAM Journal on Algebraic and Discrete Methods 4 (1983) 207-211.

Nimrod Megiddo, Arie Tamir

SIAM Journal on Algebraic and Discrete Methods 4 (1983) 207-211.

The weighted Euclidean 1-center problem

Nimrod Megiddo

Mathematics of Operations Research 8 (1983) 498-504.

Nimrod Megiddo

Mathematics of Operations Research 8 (1983) 498-504.

New results on the complexity of p-center problems

Nimrod Megiddo, Arie Tamir

SIAM Journal on Computing 12 (1983) 751-758.

Nimrod Megiddo, Arie Tamir

SIAM Journal on Computing 12 (1983) 751-758.

The maximum coverage location problem

Nimrod Megiddo, Eitan Zemel, S. Louis Hakimi

SIAM Journal on Algebraic and Discrete Methods 4 (1983) 253-261.

Nimrod Megiddo, Eitan Zemel, S. Louis Hakimi

SIAM Journal on Algebraic and Discrete Methods 4 (1983) 253-261.

Applying parallel computation algorithms in the design of serial algorithms

Nimrod Megiddo

Journal of the Association for Computing Machinery (J. ACM) 30 (1983) 852-865.

Nimrod Megiddo

Journal of the Association for Computing Machinery (J. ACM) 30 (1983) 852-865.

**1982**

Poly-log parallel algorithms for LP with an application to exploding flying objects

Nimrod Megiddo

Technical Report, Graduate School of Industrial Administration, CarnegieMellon University, November 1982

Nimrod Megiddo

Technical Report, Graduate School of Industrial Administration, CarnegieMellon University, November 1982

Is binary encoding appropriate for the problem-language relationship?

Nimrod Megiddo

Theoretical Computer Science 19 (1982) 337-341.

Nimrod Megiddo

Theoretical Computer Science 19 (1982) 337-341.

On the complexity of the one-terminal network design problem

Nimrod Megiddo

Operations Research Letters 1 (1982) 105-107.

Nimrod Megiddo

Operations Research Letters 1 (1982) 105-107.

Parallel algorithms for finding the maximum and the median almost surely in constant time,"

Nimrod Megiddo

Technical Report, Graduate School of Industrial Administration, CarnegieMellon University, 1982

Nimrod Megiddo

Technical Report, Graduate School of Industrial Administration, CarnegieMellon University, 1982

On the complexity of locating linear facilities in the plane

Nimrod Megiddo, Arie Tamir

Operations Research Letters 1 (1982) 194-197.

Nimrod Megiddo, Arie Tamir

Operations Research Letters 1 (1982) 194-197.

Linear-time algorithms for linear programming in R^3 and related problems

Nimrod Megiddo

FOCS 1982 - 23rd IEEE Annual Symposium on Foundations of Computer Science, 1982.

Nimrod Megiddo

FOCS 1982 - 23rd IEEE Annual Symposium on Foundations of Computer Science, 1982.

**1981**

An application of parallel computation to sequential computation: The problem of cost-effective resource allocation

Nimrod Megiddo

Report TWISK 202, National Research Institute for Mathematical Sciences, Council for Scientific and Industrial Research (CSIR), Pretoria, South Africa, March 1981

Nimrod Megiddo

Report TWISK 202, National Research Institute for Mathematical Sciences, Council for Scientific and Industrial Research (CSIR), Pretoria, South Africa, March 1981

An application of parallel computation to sequential computation: The problem of cost-effective resource allocation

Nimrod Megiddo

Report TWISK 202, National Research Institute for Mathematical Sciences, Council for Scientific and Industrial Research (CSIR), Pretoria, South Africa, March 1981

Nimrod Megiddo

Report TWISK 202, National Research Institute for Mathematical Sciences, Council for Scientific and Industrial Research (CSIR), Pretoria, South Africa, March 1981

Applying parallel computation algorithms in the design of serial algorithms

Nimrod Megiddo

FOCS 1981 - 22th Annual IEEE Symposium on Foundations of Computer Science, 1981

Nimrod Megiddo

FOCS 1981 - 22th Annual IEEE Symposium on Foundations of Computer Science, 1981

The complexity of searching a graph

Nimrod Megiddo, S. Louis Hakimi, Michael R. Garey, David S. Johnson, Christos H. Papadimitriou

FOCS 1981 - 22th Annual IEEE Symposium on Foundations of Computer Science

Nimrod Megiddo, S. Louis Hakimi, Michael R. Garey, David S. Johnson, Christos H. Papadimitriou

FOCS 1981 - 22th Annual IEEE Symposium on Foundations of Computer Science

An O (n log^2 n) algorithm for the kth longest path in a tree with applications to location problems

Nimrod Megiddo, Arie Tamir, Eitan Zemel, R. Chandrasekaran

SIAM Journal on Computing 10 (1981) 328-337.

Nimrod Megiddo, Arie Tamir, Eitan Zemel, R. Chandrasekaran

SIAM Journal on Computing 10 (1981) 328-337.

**1980**

Applications of modern cryptography to secret voting

Nimrod Megiddo

Technical Report, Dept. of Statistics, Tel Aviv University, Israel, 1980.

Nimrod Megiddo

Technical Report, Dept. of Statistics, Tel Aviv University, Israel, 1980.

On repeated games with incomplete information played by non-Bayesian players

Nimrod Megiddo

International Journal of Game Theory 9 (1980) 157-167.

Nimrod Megiddo

International Journal of Game Theory 9 (1980) 157-167.

**1979**

An intergenerational cake eating game

Morton I. Kamien, Nimrod Megiddo

Economics Letters 2 (1979) 781-784.

Morton I. Kamien, Nimrod Megiddo

Economics Letters 2 (1979) 781-784.

On Fulkersons conjecture about consistent labeling processes

Nimrod Megiddo, Zvi Galil

Mathematics of Operations Research 4 (1979) 265-267.

Nimrod Megiddo, Zvi Galil

Mathematics of Operations Research 4 (1979) 265-267.

Combinatorial optimization with rational objective functions

Nimrod Megiddo

Mathematics of Operations Research 4 (1979) 414-424.

Nimrod Megiddo

Mathematics of Operations Research 4 (1979) 414-424.

A fast selection algorithm and the problem of optimum distribution of effort

Zvi Galil, Nimrod Megiddo

Journal of the ACM (JACM) 26 (1979) 58-64.

Zvi Galil, Nimrod Megiddo

Journal of the ACM (JACM) 26 (1979) 58-64.

**1978**

Pursuing mobile hiders in a graph

Nimrod Megiddo, S. Louis Hakimi

Discussion Paper No. 360, Center for Mathematical Studies in Economics and Management Science, Northwestern University, 1978.

Nimrod Megiddo, S. Louis Hakimi

Discussion Paper No. 360, Center for Mathematical Studies in Economics and Management Science, Northwestern University, 1978.

On the parametric nonlinear complementarity problem

Nimrod Megiddo

Mathematical Programming Study 7 (1978) 142-150.

Nimrod Megiddo

Mathematical Programming Study 7 (1978) 142-150.

An O(n log n) algorithm for a class of matching problems

Nimrod Megiddo, Arie Tamir

SIAM Journal on Computing 7 (1978) 154-157.

Nimrod Megiddo, Arie Tamir

SIAM Journal on Computing 7 (1978) 154-157.

Computational complexity of the game theory approach to cost allocation for a tree

Nimrod Megiddo

Mathematics of Operations Research 3 (1978) 189-196.

Nimrod Megiddo

Mathematics of Operations Research 3 (1978) 189-196.

Combinatorial optimization with rational objective functions

Nimrod Megiddo

STOC 1978 - Proceedings of the tenth annual ACM symposium on Theory of Computing, 1978

Nimrod Megiddo

STOC 1978 - Proceedings of the tenth annual ACM symposium on Theory of Computing, 1978

**1977**

A fast selection algorithm and the problem of optimum distribution of effort

Zvi Galil, Nimrod Megiddo

Proceedings of Conference on Theoretical Computer Science, University of Waterloo, Canada, 1977

Zvi Galil, Nimrod Megiddo

Proceedings of Conference on Theoretical Computer Science, University of Waterloo, Canada, 1977

Mixtures of order matrices and generalized order matrices

Nimrod Megiddo

Discrete Mathematics 19 (1977) 177-181.

Nimrod Megiddo

Discrete Mathematics 19 (1977) 177-181.

A monotone linear complementarity problem with feasible solutions but no complementary solutions

Nimrod Megiddo

Mathematcal Programming 12 (1977) 131-132.

Nimrod Megiddo

Mathematcal Programming 12 (1977) 131-132.

On monotonicity in parametric linear complementarity problems

Nimrod Megiddo

Mathematical Programming 12 (1977) 60-66.

Nimrod Megiddo

Mathematical Programming 12 (1977) 60-66.

A good algorithm for lexicographically optimal flows in multi-terminal networks

Nimrod Megiddo

Bulletin of the American Mathematical Society 83 (1977) 407-409.

Nimrod Megiddo

Bulletin of the American Mathematical Society 83 (1977) 407-409.

Cyclic ordering is NP-complete

Zvi Galil, Nimrod Megiddo

Theoretical Computer Science 5 (1977) 179-182.

Zvi Galil, Nimrod Megiddo

Theoretical Computer Science 5 (1977) 179-182.

On the existence and uniqueness of solutions in nonlinear complementarity theory

Nimrod Megiddo, Masakazu Kojima

Mathematical Programming 12 (1977) 110-130.

Nimrod Megiddo, Masakazu Kojima

Mathematical Programming 12 (1977) 110-130.

**1976**

Partial and complete cyclic orders

Nimrod Megiddo

Bulletin of the American Mathematical Society 82 (1976) 274-276.

Nimrod Megiddo

Bulletin of the American Mathematical Society 82 (1976) 274-276.

A generalization of Eaves odd theorem

Nimrod Megiddo

Technical Report, Dept. of Statistics, Tel Aviv University, Israel, 1976

Nimrod Megiddo

Technical Report, Dept. of Statistics, Tel Aviv University, Israel, 1976

**1975**

Tensor decomposition of cooperative games

Nimrod Megiddo

SIAM Journal on Applied Mathematics 29 (1975) 388-405.

Nimrod Megiddo

SIAM Journal on Applied Mathematics 29 (1975) 388-405.

**1974**

Nucleoluses of compound simple games

Nimrod Megiddo

SIAM Journal on Applied Mathematics 26 (1974) 607-621.

Nimrod Megiddo

SIAM Journal on Applied Mathematics 26 (1974) 607-621.

Kernels of compound games with simple components

Nimrod Megiddo

Pacific Journal of Mathematics 50 (1974) 531-555.

Nimrod Megiddo

Pacific Journal of Mathematics 50 (1974) 531-555.

On the nonmonotonicity of the bargaining set, the kernel and the nucleolus of a game

Nimrod Megiddo

SIAM Journal on Applied Mathematics 27 (1974) 355-358

Nimrod Megiddo

SIAM Journal on Applied Mathematics 27 (1974) 355-358

Optimal flows in networks with multiple sources and sinks

Nimrod Megiddo

Mathematical Programming 7 (1974) 97-107.

Nimrod Megiddo

Mathematical Programming 7 (1974) 97-107.

**1971**

The kernel and the nucleolus of a product of simple games

Nimrod Megiddo

Israel Journal of Mathematics 9 (1971) 210-221.

Nimrod Megiddo

Israel Journal of Mathematics 9 (1971) 210-221.

**Year Unknown**

Maximizing concave functions in fixed dimension, Research Report RJ 7656 (71103), IBM Almaden Research Center, San Jose, 1990

E Cohen, N Megiddo

E Cohen, N Megiddo

*Also in this volume.*, 0
E cient nearest neighbour indexing based on a collection of space-filling curves

N Megiddo, U Shaft

Technical Report, 0

N Megiddo, U Shaft

Technical Report, 0

Discovery-driven exploration of OLAP data cubes. Research Report RJ 10102 (91918), IBM Almaden Research Center, San Jose, CA 95120, January 1998

S Sarawagi, R Agrawal, N Megiddo

S Sarawagi, R Agrawal, N Megiddo, 0

S Sarawagi, R Agrawal, N Megiddo

S Sarawagi, R Agrawal, N Megiddo, 0

Theoretical convergence of large--step--primal--dual interior point algorithms for linear programming. Research Report RJ 7872 (72532), IBM Almaden Research Division, San Jose, CA 95120-6099, USA, 1990

M Kojima, N Megiddo, S Mizuno

M Kojima, N Megiddo, S Mizuno

*Mathematical Programming*, 0
A variation on Karmarkar’s algorithm

N Megiddo

N Megiddo

*Preliminary Report, IBM Research Division, Almaden Research Center, San Jose, CA*, 95120--6099