Nimrod Megiddo  Nimrod Megiddo photo       

contact information

Distinguished Research Staff Member
Almaden Research Center, San Jose, CA, USA
  +1dash408dash927dash1786

links



2008

Efficient coalition detection in traitor tracing
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

Dynamic faceted search for discovery-driven analysis
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
The VLDB Journal 16(1), 55--76, Springer, 2007


Continuity properties of equilibrium prices and allocations in linear Fisher markets
N Megiddo, V V Vazirani
LECTURE NOTES IN COMPUTER SCIENCE4858, 362, Springer, 2007

Online learning with prior knowledge
E Hazan, N Megiddo
Lecture Notes in Computer Science4539, 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
Lecture Notes in Computer Science3896, 1092, Springer, 2006

Efficient traitor tracing
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

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.

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


2005

Exploration-exploitation tradeoffs for experts algorithms in reactive environments
D Farias de, N Megiddo
Advances in neural information processing systems17, 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)

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


2004

Linear Programming
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
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

A Simple Adaptive Cache Algorithm Outperforms LRU
N Megiddo, D S Modha
IBM Research Report, Computer Science, 2003

One up on LRU
N Megiddo, D S Modha
login--The Magazine of the USENIX Association28, 7--11, 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

ARC: A self-tuning, low overhead replacement cache
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
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.


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

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

Improved algorithms and analysis for secretary problems and generalizations
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


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

On structured Markov decision processes in continuous state space
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
Theoretical Computer Science 233(1-2), 297--308, Elsevier, 2000

An analytical model for loop tiling and its solution
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


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


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

Using fast matrix multiplication to find basic solutions
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.

A modified layered-step interior-point algorithm for linear programming
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

Discovery-driven exploration of OLAP data cubes
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
IBM Research Report, Citeseer, 1997

Efficient nearest neighbor indexing based on a collection of space-filling curves
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.

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

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.

Linear programming in low dimensions
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

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


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.

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.

Segmenting and representing background in color images
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

A linear programming instance with many crossover events
S Mizuno, N Megiddo, T Tsuchiya
Journal of Complexity 12(4), 474--479, Elsevier, 1996


On the geometric separability of boolean functions
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.

Efficient computation of equilibria for extensive two-person games
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


1994


On probabilistic machines, bounded rationality, and average-case complexity
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

Constructing Small Sample Spaces Satisfying Given Constants
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.

Improved algorithms for linear inequalities with two variables per inequality
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.

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.

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


1993

Horizontal and vertical decomposition in interior point methods for linear programs
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
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
contract 14(91-C), 0026, Citeseer, 1993

Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs
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.

Maximizing concave functions in fixed dimension
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.

A general framework of continuation methods for complementarity problems
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

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.

A primal—dual infeasible-interior-point algorithm for linear programming
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.


1992

A Lagrangian Relaxation Method for Approximating the Analytic Center of a Polytope
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.

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

A note on approximate linear programming
Nimrod Megiddo
Information Processing Letters 2 (1992) 53

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

An interior point potential reduction algorithm for the linear complementarity problem
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.


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


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.

Algorithms and complexity analysis for some flow problems
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

Recognizing properties of periodic graphs
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

Approximation algorithms for hitting objects with straight lines
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

A note on total functions, existence theorems, and computational complexity
Nimrod Megiddo, Christos H. Papadimitriou
Theoretical Computer Science 81 (1991) 317-324.

On finding primal-and dual-optimal bases
Nimrod Megiddo
ORSA Journal on Computing 3 (1991) 63-65.

Homotopy continuation methods for nonlinear complementarity problems
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

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
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

A unified approach to interior point algorithms for linear complementarity problems: A summary
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.

On solving the linear programming problem approximately
Nimrod Megiddo
Contemporary Mathematics 114 (1990) 35-50.

A logic for reasoning about probabilities
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.

A logic for reasoning about probabilities.
R Fagin, J Y Halpern, N Megiddo
INF. COMPUT. 87(1), 78--128, Citeseer, 1990


1989

Progress in mathematical programming
N Megiddo
oai.dtic.mil, Springer New York etc., 1989

Extending NC and RNC algorithms
Nimrod Megiddo
Algorithmica 4 (1989) 511-517.

On computable beliefs of rational machines
N Megiddo
Games and Economic Behavior, 1989

On orientations and shortest paths
Refael Hassin, Nimrod Megiddo
Linear Algebra and Its Applications 114/115 (1989) 589-602.

On the ball spanned by balls
Nimrod Megiddo
Discrete and Computational Geometry 4 (1989) 605-610.

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


Boundary behavior of interior point algorithms in linear programming
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


1988

A Note on Complexity of P-Matrix L с P and Computing an Equilibrium
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
IBM Almaden Research Center, San Jose, California, 1988

On finding primal $\{$and dual $\{$optimal bases. RJ 6328 (61997)
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.

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

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

A note on Karmarkars projective transformation
Nimrod Megiddo
IBM Almaden Research Center, San Jose, California, , December 1988

On the epsilon-perturbation method for avoiding degeneracy
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.

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

On the complexity of polyhedral separability
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.


1987

Report on the conference: Progress in mathematical programming
N Megiddo
Technical Report, 1987

Turing Machines Play the Finitely Repeated Prisoners' Dilemma," IBM Almaden Research Center, San Jose California
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

Linear Programming (1986)
Nimrod Megiddo
Annual Review of Computer Science 2 (1987) 119-145.

On the complexity of linear programming
Nimrod Megiddo
Advances in Economic Theory: Fifth world congress, T. Bewley, ed., 1987


1986

Remarks on bounded rationality [Z]. IBM research report RJ 54310
N Megiddo
Computer Science, 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
Games and Economic Behavior1, 144--69, 1986

Remarks on bounded rationality
N Megiddo
IBM research paper RJ5270, Citeseer, 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

Dynamic location problems
N Megiddo
Annals of Operations Research 6(10), 311--319, Springer, 1986



Introduction: New approaches to linear programming
N Megiddo
Algorithmica 1(1), 387--394, Springer, 1986

A note on degeneracy in linear programming
N Megiddo
Mathematical Programming 35(3), 365--367, Springer, 1986


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


1985

A note on sensitivity analysis in algebraic algorithms
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.



A two-resource allocation problem solvable in linear time
Nimrod Megiddo, Tetsuo Ichimori
Mathematics of Operations Research 10 (1985) 7-16.

Partitioning with two lines in the plane
Nimrod Megiddo
Journal of Algorithms 6 (1985) 430-433.

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

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.


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

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.

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.

On the complexity of some common geometric location problems
Nimrod Megiddo, Kenneth J. Supowit
SIAM Journal on Computing 13 (1984) 182-196.


1983



Finding least-distances lines.
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.

New results on the complexity of p-center problems
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.

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.


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



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

On the complexity of locating linear facilities in the plane
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.


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

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

Applying parallel computation algorithms in the design of serial algorithms
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

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.


1980

Applications of modern cryptography to secret voting
Nimrod Megiddo
Technical Report, Dept. of Statistics, Tel Aviv University, Israel, 1980.

Path-independent choices
Ehud Kalai, Nimrod Megiddo
Econometrica 48 (1980) 781-784.



1979

An intergenerational cake eating game
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.

Combinatorial optimization with rational objective functions
Nimrod Megiddo
Mathematics of Operations Research 4 (1979) 414-424.



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.

On the parametric nonlinear complementarity problem
Nimrod Megiddo
Mathematical Programming Study 7 (1978) 142-150.

Edge three-coloring of tournaments
Nimrod Megiddo
SIAM Review 20 (1978) 593

An O(n log n) algorithm for a class of matching problems
Nimrod Megiddo, Arie Tamir
SIAM Journal on Computing 7 (1978) 154-157.



Combinatorial optimization with rational objective functions
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




A good algorithm for lexicographically optimal flows in multi-terminal networks
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.

On the existence and uniqueness of solutions in nonlinear complementarity theory
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.

A generalization of Eaves odd theorem
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.


1974

Nucleoluses of compound simple games
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.




1971

The kernel and the nucleolus of a product of simple games
Nimrod Megiddo
Israel Journal of Mathematics 9 (1971) 210-221.


Year Unknown

Adaptive Replacement Cache
N Megiddo, DS Modha
almaden. ibm .com, 0

Maximizing concave functions in fixed dimension, Research Report RJ 7656 (71103), IBM Almaden Research Center, San Jose, 1990
E Cohen, N Megiddo
Also in this volume., 0

Dynamic location problems. IBM Almaden Research Center
N Megiddo
Technical Report, 0

E cient nearest neighbour indexing based on a collection of space-filling curves
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

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
Mathematical Programming, 0

A Simple Adaptive Algorithm Outperforms LRU
N Megiddo, D S Modha
IBM Research Report, RJ10284

A variation on Karmarkar’s algorithm
N Megiddo
Preliminary Report, IBM Research Division, Almaden Research Center, San Jose, CA, 95120--6099