Abstract Fast Algorithms for Finding Randomized Strategies in Game Trees (2009)
Daphne Koller, Nimrod Megiddo, Bernhard Von Stengel
Interactions among agents can be conveniently described by game trees. In order to analyze a game, it is important to derive optimal (or equilibrium) strategies for the different players. The...
A reactive environment is one that responds to the actions of an agent rather than evolving obliviously. In reactive environments, experts algorithms must balance exploration and exploitation of...
The so-called “experts algorithms ” constitute a methodology for choosing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the...
Formatting Instructions for MOR Articles informs ® DOI 10.1287/moor.xxxx.xxxx c○20xx INFORMS (2008)
The abstract is limited to one paragraph of at most 150 words. Note that it is not indented. It should contain no references and no equations. Following the abstract please enter the following items:...
� Load Balancing � Overall Optimal Performance Solution Approach (2008)
Jun Rao, Chun Zhang, Nimrod Megiddo, Guy M. Lohman, Key Idea
� Different queries, best partitions differ � Same query, multiple tables join on different columns � Local joins, aggregation etc.
A reactive environment is one that responds to the actions of an agent rather than evolving obliviously. In reactive environments, experts algorithms must balance exploration and exploitation of...
Abstract Range Queries in OLAP Data Cubes (2008)
Ching-tien Ho, Rakesh Agrawal, Nimrod Megiddo, Ramakrishnan Srikant
A range query applies an aggregation operation over all selected cells of an OLAP data cube where the selection is speci ed by providing ranges of values for numeric dimensions. We present fast...
The so-called “experts algorithms ” constitute a methodology for choosing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the...
London Paris Tokyo CHAPTER 8 Pathways to the Optimal Set in Linear Programming (2008)
Abstract. This chapter presents continuous paths leading to the set of optimal solutions of a linear programming problem. These paths are derived from the weighted logarithmic barrier function. The...
Discrete Comput Geom 3:325-337 (1988) On the Complexity of Polyhedral Separability (2008)
Abstract. It is NP-complete to recognize whether two sets of points in general space can be separated by two hyperplanes. It is NP-complete to recognize whether two sets of points in the plane can be...
A Note on Sensitivity Analysis in Algebraic Algorithms (2008)
Nimrod Megiddo, Nimrod Megiddo, Nimrod Megiddo
This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its...
Refael Hassin, Nimrod Megiddo, G. Rothblum
Dedicated to Alan J. Hoffman on the occasion of his 65th birthday.
Categories and Subject Dcscriptors: G.l.O [Numerical Analysis]: General-parallel algontlznts: (2008)
Abstract. For any futed dimension d, the linear programming problem with IZ inequality con-straints can be solved on a probabilistic CRCW PRAM with O(n) processors almost surely in constant time. The...
Smale proposed a framework for applying Newton's method to the linear p gramming problem. It is shown that his method is closely related to recent inte point methods, in the sense that it also...
ABSTRATI. An algorithm IS developed whtch finds the nth largeat element of a Ilnearly ordered \el S. glven In the form of rn pairwise dlsjo~nt subsets. Each of the rn subsets satisfies the property...
Printed in U.S.A. THE WEIGHTED EUCLIDEAN 1-CENTER PROBLEM*? (2008)
algorithm for the problem of finding a point (x, y) in the plane that minimizes the maximal weighted distance to a point in a set of n given points. The algorithm can be extended to higher...
Online Learning with Prior Knowledge (2008)
Abstract. The standard so-called experts algorithms are methods for utilizing a given set of “experts ” to make good choices in a sequential decision-making problem. In the standard setting of...
Pmrtrd r n U S..4. BOUNDARY BEHAVIOR OF INTERIOR POINT ALGORITHMS IN LINEAR PROGRAMMING*~ (2008)
This paper studies the boundary behavior of some interior point algorithms for linear programming. The algorithms considered are Karmarkar's projective rescaling algorithm, the linear rescaling...
ABSTRACT:Complexity results are obtained with regard to problems of finding sol-utions to set of linear inequalities which are compatible with some set-functions and a prescribed intersection graph....
Discrete Cornput Geom 4:605-610 (1989) G~Gsldid On the Ball Spanned by Balls (2008)
Abstract. The procedure for linear programming in linear time in fixed dimension is extended to solve in linear time certain nonlinear problems. Examples are the problem of finding the smallest ball...
Primed in U.SA. COMPUTATIONAL COMPLEXITY OF THE GAME THEORY APPROACH TO COST ALLOCATION FOR A (2008)
Nimrod Megiddo, Tel Aoio Unioersity
In the game theory approach to the problem of allocating cost, the users of a facility are viewed as players in a cooperative n-person game. It is the nature of cooperative games that the power of...
Dynamic faceted search for discovery-driven analysis (2008)
Dash, Debabrata, Rao, Jun, Megiddo, Nimrod, Ailamaki, Anastasia, Lohman, Guy M.
Miklos Ajtai, Nimrod Megiddo, Orli Waarts
In the classical secretary problem, n objects from an ordered set arrive in random order, and one has to accept k of them so that the final decision about each object is made only on the basis of its...
Extending NC and RNC Algorithms (2007)
this paper. Consider a parametric version of the shortest path problem as follows. Suppose the edges of a graph on n vertices have lengths d ij = d ij (t) = a ij t + b ij (assuming
Abstract. The subject of this paper is finding small sample spaces for joint distributions of n discrete random variables. Such distributions are often only required to obey a certain limited set of...
On Solving the Linear Programming Problem Approximately (2007)
. This paper studies the complexity of some approximate solutions of linear programming problems with real coefficients. 1. Introduction The general linear programming problem is to maximize a linear...
A Note on Karmarkar's Projective Transformation (2007)
. This note corrects a certain inaccuracy in the discussion of the projective transformation employed by Karmarkar in the reduction of a general linear programming to the form required for his...
Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno
x = 1g is characterized by a saddle point condition min y2R m max x2S++ g(x; y) = max x2S++ min y2R
Abstract. Corresponding to the linear program: Maximize c (2007)
Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno, Susumu Shindoh
x subject to Ax = a; Bx = b; x 0; we introduce two functions in the penalty parameter t? 0 and the Lagrange relaxation parameter vector w, ~ f p (t; w) = maxfc T x \Gamma w T
The Minimum Reservation Rate Problem (2007)
In Digital Audio, David P. Anderson, Nimrod Megiddo, Moni Naor
David P. Anderson Nimrod Megiddo Moni Naor April 1993 Abstract.
A Note on Karmarkar's ProjectiveTransformation (2007)
Nimrod Megiddo December, Nimrod Megiddo
This note corrects a certain inaccuracy in the discussion of the projective transformation employed by Karmarkar in the reduction of a general linear programming to the form required for his...
Extending NC and RNC Algorithms (2007)
Nimrod Megiddo Atechnique, Nimrod Megiddo
this paper. Consider a parametric version of the shortest path problem as follows. Suppose the edges of a graph on n vertices have lengths d ij = d ij (t)=a ij t + b ij (assuming The IBM Almaden...
On Solving the Linear Programming Problem Approximately (2007)
Nimrod Megiddo Revised, Nimrod Megiddo
This paper studies the complexity of some approximate solutions of linear programming problems with real coefficients.
On the-perturbation Method for Avoiding Degeneracy (2007)
Method For Avoiding, Nimrod Megiddo, R. Ch, Rasekaran Y
Although it is NP-complete to decide whether a linear programming problemis degenerate, the method can be used to reduce in polynomial time any linear programming problemwith rational coefficients to...
Continuity properties of equilibrium prices and allocations in linear fisher markets (2007)
Nimrod Megiddo, Vijay V. Vazirani
Abstract. Continuity of the mapping from initial endowments and utilities to equilibria is an essential property for a desirable model of an economy – without continuity, small errors in the...
Combining expert advice in reactive environments (2006)
“Experts algorithms ” constitute a methodology for choosing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the environment. An...
ARC: a self-tuning, low overhead replacement cache (2003)
Megiddo, Nimrod, Modha, Dharmendra S.
USENIX Conference on file and storage technologies (2nd: 2003: San Francisco, CA)
ARC: A self-tuning, low overhead replacement cache (2003)
Nimrod Megiddo, Dharmendra S. Modha
Abstract--- We consider the problem of cache management in a demand paging scenario with uniform page sizes. We propose a new cache management policy, namely, Adaptive Replacement Cache (ARC), that...
ARC: A self-tuning, low overhead replacement cache (2003)
Nimrod Megiddo, Dharmendra S. Modha
Permission is granted for noncommercial reproduction of the work for educational or research purposes.
ARC: A self-tuning, low overhead replacement cache (2003)
Nimrod Megiddo, Dharmendra S. Modha
Abstract — We consider the problem of cache management in a demand paging scenario with uniform page sizes. We propose a new cache management policy, namely, Adaptive Replacement Cache (ARC), that...
How to Combine Expert (or Novice) Advice (2003)
When Actions Impact, Nimrod Megiddo
The so-called "experts algorithms" constitute a methodology for choosing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the...
Automating physical database design in a parallel database (2002)
Jun Rao, Chun Zhang, Guy Lohman, Nimrod Megiddo, Jun Rao, Chun Zhang, ...
LIMITED DISTRIBUTION NOTICE: This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. Ithas
Automating physical database design in a parallel database (2002)
Jun Rao, Chun Zhang, Nimrod Megiddo
Physical database design is important for query performance in a shared-nothing parallel database system, in which data is horizontally partitioned among multiple independent nodes. We seek to...
An improved predictive accuracy bound for averaging classifiers (2001)
John Langford, Matthias Seeger, Nimrod Megiddo
We present an improved bound on the difference between training and test errors for voting classiers. This improved averaging bound provides a theoretical justication for popular averaging techniques...
Progress in Mathematical Programming. (1998)
Most of the progress reported at the conference was on the theoretical side. Several new polynomial algorithms for linear programming were presented. The common feature to most of the new polynomial...
Discovery-driven Exploration of OLAP Data Cubes (1998)
Sunita Sarawagi, Rakesh Agrawal, Nimrod Megiddo
. Analysts predominantly use OLAP data cubes to identify regions of anomalies that may represent problem areas or new opportunities. The current OLAP systems support hypothesis-driven exploration of...
Discovering Predictive Association Rules (1998)
Nimrod Megiddo, Ramakrishnan Srikant
Association rule algorithms can produce a very large number of output patterns. This has raised questions of whether the set of discovered rules "overfit" the data because all the patterns...
Discovery-driven Exploration of OLAP Data Cubes (1998)
Sunita Sarawagi, Rakesh Agrawal, Nimrod Megiddo
Abstract. Analysts predominantly use OLAP data cubes to identify regions of anomalies that may represent problem areas or new opportunities. The current OLAP systems support hypothesis-driven...
A conjugate direction method for approximating the analytic center of a polytope (1998)
Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno
The analytic center ω of an n-dimensional polytope P={x∈Rn:aiTx−bi≥0 (i=1,2,⋯,m)} with a nonempty interior Pint is defined as the unique minimizer of the logarithmic potential function...
Final Report on ONR Contract N00014-94-C-0007. (1997)
The subjects of research under this contract were topics in linear programming and related problems. The problems we have investigated are quite diverse.
Optimal Weighted Loop Fusion for Parallel Programs (1997)
Much of the computation involved in parallel programs occurs within loops, either nested loops as in parallel scientific applications or collections of loops as in stream-based applications. Loop...
Range Queries in OLAP Data Cubes (1997)
Ching-Tien Ho, Rakesh Agrawal, Nimrod Megiddo, Ramakrishnan Srikant
A range query applies an aggregation operation over all selected cells of an OLAP data cube where the selection is specified by providing ranges of values for numeric dimensions. We present fast...
Range Queries in OLAP Data Cubes (1997)
Ching-Tien Ho, Rakesh Agrawal, Nimrod Megiddo, Ramakrishnan Srikant
A range query applies an aggregation operation over all selected cells of an OLAP data cube where the selection is specified by providing ranges of values for numeric dimensions. We present fast...
Techniques for Speeding up Range-Max Queries in OLAP Data Cubes (1997)
Ching-Tien Ho, Rakesh Agrawal, Nimrod Megiddo, Jyh-jong Tsay
A range-max query obtains the maximum over all selected cells of a data cube where the selection is specified by providing ranges of values for numeric dimensions. Our general approach to speeding up...
On the geometric separability of Boolean functions (1996)
We investigate the complexity of the MEMBERSHIP problem for some geometrically defined classes of Boolean functions, i.e., the complexity of deciding whether a Boolean function given in DNF belongs...
Finding mixed strategies with small supports in extensive form games (1996)
The complexity of algorithms that compute strategies or operate on them typically depends on the representation length of the strategies involved. One measure for the size of a mixed strategy is the...
Efficient Computation of Equilibria for Extensive Two-Person Games (1996)
Daphne Koller, Nimrod Megiddo, Bernhard Von Stengel
. The Nash equilibria of a two-person, non-zero-sum game are the solutions of a certain linear complementarity problem (LCP). In order to use this for solving a game in extensive form, it is first...
Efficient Computation of Equilibria for Extensive Two-Person Games (1996)
Two-person Games, Daphne Koller, Nimrod Megiddo, Bernhard Von Stengel
. The Nash equilibria of a two-person, non-zero-sum game are the solutions of a certain linear complementarity problem (LCP). In order to use this for solving a game in extensive form, the game must...
Finding a line of sight thru boxes in d-space in linear time (1996)
Nimrod Mcgiddo, Nimrod Megiddo, Nimrod Megiddo
lbb br htem fm pbliUin msi & of IBM ud rill @My h. cqyd#W if ps for phlk.inl. 11 *I ham i d r Rqmn fw arb dirniuia of iU crmms. In vim of the tmsfer
Masakazu Kojima A't, Nimrod Megiddo, Shlnjl Mizuno
The analytic center o of an n-dimensional polytope P = {x E R": aTx- b, 2 0 (i = 1.2,...,m)} with a nonempty interior P,,, is defined as the unique minimizer of the logarithmic potential...
Efficient computation of equilibria for extensive two-person games (1996)
Daphne Koller, Nimrod Megiddo, Bernhard Von Stengel
The Nash equilibria of a two-person, non-zero-sum game are the solutions of a certain linear complementarity problem (LCP). In order to use this for solving a game in extensive form, it is rst...
Improved algorithms and analysis for secretary problems and generalizations (1995)
Miklos Ajtai, Nimrod Megiddo, Orli Waarts
In the classical secretary problem, n objects from an ordered set arrive in random order, and one has to accept k of them so that the nal decision about each objectismadeonlyonthe basis of its rank...
Improved Algorithms and Analysis for Secretary Problems and Generalizations (1995)
Miklos Ajtai, Nimrod Megiddo, Orli Waarts
this paper we show that, surprisingly, the two goals are in fact in conflict (see Section 1.2). It can be proven by backward induction that there exists an optimal policy for minimizing the expected...
Finding Mixed Strategies with Small Supports in Extensive Form Games (1995)
The complexity of algorithms that compute strategies or operate on them typically depends on the representation length of the strategies involved. One measure for the size of a mixed strategy is the...
ARTICLE NO. 0051 Efficient Computation of Equilibria for Extensive (1994)
Two-person Games, Daphne Koller, Nimrod Megiddo, Bernhard Von Stengel
The Nash equilibria of a two-person, non-zero-sum game are the solutions of a certain linear complementarity problem (LCP). In order to use this for solving a game in extensive form, the game must...
Fast Algorithms for Finding Randomized Strategies in Game Trees (1994)
Daphne Koller, Nimrod Megiddo, Bernhard Von Stengel
Interactions among agents can be conveniently described by game trees. In order to analyze a game, it is important to derive optimal (or equilibrium) strategies for the different players. The...
A General Framework of Continuation Methods for Complementarity Problems (1994)
Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno
. A new class of continuation methods is presented which, in particular, solve linear complementarity problems with copositive-plus and L -matrices. Let a; b 2 R n be nonnegative vectors. We embed...
A Sublinear Parallel Algorithm for Stable Matching (1994)
Tomás Feder, Nimrod Megiddo, Serge A. Plotkin
. Parallel algorithms for various versions of the stable matching problem are presented. The algorithms are based on the primal-dual interior pathfollowing method for linear programming. The main...
A Sublinear Parallel Algorithm for Stable Matching (1994)
Tom'as Feder Nimrod, Nimrod Megiddo, Serge A. Plotkin
this paper we consider networks made of gates of constant size. We focus of non-expansive networks (to be defined below). The problems of evaluating the gate to which a network converges, and of...
Fast Algorithms for Finding Randomized Strategies in Game Trees (1994)
Daphne Koller, Nimrod Megiddo, Bernhard Von Stengel
Interactions among agents can be conveniently described by game trees. In order to analyze a game, it is important to derive optimal (or equilibrium) strategies for the different players. The...
Fast Algorithms for Finding Randomized Strategies in Game Trees (1994)
Daphne Koller, Nimrod Megiddo, Bernhard Von Stengel
Interactions among agents can be conveniently described by game trees. In order to analyze a game, it is important to derive optimal (or equilibrium) strategies for the different players. The...
A Sublinear Parallel Algorithm for Stable Matching (1994)
Tom'as Feder, Nimrod Megiddo, Serge A. Plotkin
this paper we consider networks made of gates of constant size. We focus of non-expansive networks (to be defined below). The problems of evaluating the gate to which a network converges, and of...
A Sublinear Parallel Algorithm for Stable Matching (1994)
Tom'as Feder Nimrod, Tomas Feder, Nimrod Megiddo, Serge A. Plotkin
this paper we consider networks made of gates of constant size. We focus of non-expansivenetworks (to be defined below). The problems of evaluating the gate to which a network converges, and of...
A sublinear parallel algorithm for stable matching (1994)
Tomas Feder, Nimrod Megiddo, Serge A. Plotkin, Communicated F. Yao
A parallel algorithm for the stable matching problem is presented. The algorithm is based on the primal-dual interior path-following method for linear programming. The main result is that a stable...
A general framework of continuation methods for complementarity problems (1993)
Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno
Abstract. A new class of continuation methods is presented which, in particular, solve linear complementarity problems with copositive-plus and L-matrices. Let a � b 2 R n be nonnegative vectors....
Using fast matrix multiplication to find basic solutions (1993)
Peter A. Beling, Nimrod Megiddo
Abstract. We consider the problem of finding a basic solution to a system of linear constraints (in standard form) given a non-basic solution to the system. We show that the known arithmetic...
The minimum reservation rate problem in digital audio/video systems (1993)
Nimrod Megiddo, Moni Naor, David P. Anderson
The "Minimum Reservation Rate Problem " arises in distributed systems for handling digital audio and video data. The problem is to find the minimum rate at which data must be...
Dorit S. Hochbaum, Nimrod Megiddo, Joseph Naor, Arie Tamir
Abstract. The problem of integer programming in bounded variables, over constraints with no more than two variables in each constraint is NP-complete, even when all variables are binary. This paper...
Horizontal and vertical decomposition in interior point methods for linear programs (1993)
Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno, Susumu Shindoh
Corresponding to the linear program: Maximize c T x subject to Ax = a � Bx = b � x 0� we introduce two functions in the penalty parameter t>0 and the Lagrange relaxation parameter vector w,...
Linear Time Algorithms for Some Separable Quadratic Programming Problems (1993)
. A large class of separable quadratic programming problems is presented. The problems in the class can be solved in linear time. The class includes the separable convex quadratic transportation...
A General NP-Completeness Theorem (1993)
. A detailed model of a random access computation over an abstract domain is presented, and the existence of an NP-complete problem is proven under broad conditions which unify Cook's theorem...
The Minimum Reservation Rate Problem in Digital Audio/Video Systems (Extended Abstract) (1993)
David P. Anderson, Nimrod Megiddo, Moni Naor
) David P. Anderson Nimrod Megiddo y Moni Naor z April 1993 Abstract. The "Minimum Reservation Rate Problem" arises in distributed systems for handling digital audio and video data. The...
Maximizing Concave Functions in Fixed Dimension (1993)
In [3, 5, 2] the authors introduced a technique which enabled them to solve the parametric minimum cycle problem with a fixed number of parameters in strongly polynomial time. In the current paper 1...
Maximizing Concave Functions in Fixed Dimension (1993)
In [3, 5, 2] the authors introduced a technique which enabled them to solve the parametric minimum cycle problem with a fixed number of parameters in strongly polynomial time. In the currentpaper we...
Constructing Small Sample Spaces Satisfying Given Constraints (1993)
The subject of this paper is finding small sample spaces for joint distributions of n discrete random variables. Such distributions are often only required to obey a certain limited set of...
Linear Time Algorithms for Some Separable Quadratic Programming Problems (1993)
A large class of separable quadratic programming problems is presented. The problems in the class can be solved in linear time. The class includes the separable convex quadratic transportation...
Abstract. It is shown that for any fixed number of variables, the linear programming problems with n linear inequalities can be solved deterministically by n parallel processors in sub-logarithmic...
The complexity oftwo-person zero-sum games in extensive form (1992)
This paper investigates the complexity of nding max-min strategies for nite two-person zero-sum games in the extensive form. The problem of determining whether a player with imperfect recall can...
A Note on Approximate Linear Programming (1992)
. M. Serna recently proved that approximating linear programming is log-space complete for P. This note shows a direct reduction of the exact problem to Serna's approximate one. Consider the...
Masakazu Kojima Nimrod, Masakazu Kojima Y, Nimrod Megiddo, Shinji Mizuno
This paper proposes two sets of rules, Rule G and Rule P, for controlling step lengths in a generic primal-dual interior point method for solving the linear programming problem in standard form and...
A Lagrangian Relaxation Method for Approximating the Analytic Center of a Polytope (1992)
Masakazu Kojima Nimrod, Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno
The analytic center of a polytope P+ = fx x =1g is characterized by a saddle point condition m max g(x# y) = max g(x# y) # on the Lagrangian function log x j where A 2 R , and S++ = fx ? 0 x j =1g....
Dorit S. Hochbaum, Nimrod Megiddo, Joseph Naor, Arie Tamir
The problem of integer programming in bounded variables, over constraints with no more than twovariables in each constraint is NP-complete, even when all variables are binary. This paper deals with...
Tail Estimates for the Space Complexity of Randomised Incremental Algorithms (1992)
Mehlhorn, Kurt, Sharir, Micha, Welzl, Emo, Frederickson, Grag, Graham, Ron, Hochbaum, Dorit S., ...
Dynamic Point Location in General Subdivisions (1992)
Baumgarten, Hanna, Jung, Hermann, Mehlhorn, Kurt, Frederickson, Grag, Graham, Ron, Hochbaum, Dorit S., ...
On Finding Primal- and Dual-Optimal Bases (1991)
Abstract. We show that if there exists a strongly polynomial time algorithm that nds a basis which is optimal for both the primal and the dual problems, given an optimal solution for one of the...
Homotopy continuation methods for nonlinear complementarity problems (1991)
Masakazu Kojima, Nimrod Megiddo, Toshihito Noma
Abstract. A complementarity problem with a continuous mapping f from the n-dimensional Euclidean space R n into itself can be written as the system of equations F (x � y) =0 and (x � y) 0: Here F...
A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems (1991)
Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, Akiko Yoshise
Abstract. This note summarizes a report with the same title, where a study was carried out regarding a unified approach, proposed by Kojima, Mizuno and Yoshise, for interior point algorithms for the...
A conjugate direction method for approximating the analytic center of a polytope (1991)
Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno
Abstract. The analytic center! of an n-dimensional polytope P = fx 2 R n: a T i x; bi 0(i =1�2 �...�m)g with a nonempty interior Pint is de ned as the unique minimizer of the logarithmic...
Approximation Algorithms For Hitting Objects With Straight Lines (1991)
. In the hitting set problem one is given m subsets of a finite set N and one has to find an X ae N of minimum cardinality that "hits" (intersects) all of them. The problem is NP-hard. It...
On Finding Primal- and Dual-Optimal Bases (1991)
. We show that if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and the dual problems, given an optimal solution for one of the problems,...
Linear Programming (For the Encyclopedia of Microcomputers) (1991)
asserts that (i) for any x that satisfies the constraints of the primal and for any y that satisfies the conditions of the dual, c T x b T y, and (ii) if there exist such x and y, then the maximum of...
A Conjugate Direction Method for Approximating the Analytic Center of a Polytope (1991)
Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno
. The analytic center ! of an n-dimensional polytope P = fx 2 R n : a T i x \Gamma b i 0 (i = 1; 2; . . . ; m)g with a nonempty interior P int is defined as the unique minimizer of the logarithmic...
Exact Computation of Optimal Inventory Policies over an Unbounded Horizon (1991)
. An inventory scheduling model with forbidden time intervals is analyzed. The objective is to minimize the long-term average cost per time unit. Unlike most of the literature on inventory theory, no...
Approximation Algorithms For Hitting Objects With Straight Lines (1991)
Abstract. In the hitting set problem one is given m subsets of a finite set N and one has to find an X ae N of minimum cardinality that "hits" (intersects) all of them. The problem is...
Linear Programming (For the Encyclopedia of Microcomputers) (1991)
Linear programming is one of the most successful disciplines within the eld of operations research. In its standard form, the linear programming problem calls for nding nonnegative x1 �...�xn so...
t'r~rrnred m U.S.A. HOMOTOPY CONTINUATION METHODS FOR NONLINEAR COMPLEMENTARITY PROBLEMS*' (1991)
Masakazu Kojima, Nimrod Megiddo, Toshihito Noma
A complementarity problem with a continuous mapping f from Rn into itself can be written as the system of equations F(x, y) = 0 and (x, y)> 0. Here F is the mapping from R ~ " into itself...
Abstract. M. Serna recently proved that approximating linear programming is log-space complete for P. This note shows a direct reduction of the exact problem to Serna's approximate one. Consider...
On the complexity of some geometric problems in unbounded dimension (1990)
This paper examines the complexity of several geometric problems due to un-bounded dimension. The problems considered are: (i) minimum cover of points by unit cubes, (ii) minimum cover of points by...
Parallel linear programming in fixed dimension almost surely in constant time (1990)
Abstract. For any xed dimension d, the linear programming problem with n inequality constraints can be solved on a probabilistic CRCW PRAM with O(n) processors almost surely in constant time. The...
Linear programming with two variables per inequality in poly-log time (1990)
George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran
Abstract. The parallel time complexity of the linear programming problem with at most two variables per inequality is discussed. Let n and m denote the number of variables and the number of...
Linear programming with two variables per inequality in poly-log time (1990)
George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran
Abstract. The parallel time complexity of the linear programming problem with at most two variables per inequality is discussed. Let n and m denote the number of variables and the number of...
Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, Akiko Yoshise
This note summarizes a report with the same title, where a study was carried out regarding a unified approach, proposed by Kojima, Mizuno and Yoshise, for interior point algorithms for the linear...
Linear Programming with Two Variables per Inequality in Poly-Log Time (1990)
George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran
. The parallel time complexity of the linear programming problem with at most two variables per inequality is discussed. Let n and m denote the number of variables and the number of inequalities,...
Linear Programming with Two Variables per Inequality in Poly-Log Time (1990)
George Lueker, Nimrod Megiddo, Vijaya Ramachandran
. The parallel time complexity of the linear programming problem with at most two variables per inequality is discussed. Let n and m denote the number of variables and the number of inequalities,...
The Complexity of Two-Person Zero-Sum Games in Extensive Form (1990)
This paper investigates the complexity of finding max-min strategies for finite two-person zero-sum games in the extensive form. The problem of determining whether a player with imperfect recall can...
On the Complexity of Some Geometric Problems in Unbounded Dimension (1990)
This paper examines the complexity of several geometric problems due to unbounded dimension. The problems considered are: (i) minimum cover of points by unit cubes, (ii) minimum cover of points by...
Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time (1990)
. For any fixed dimension d, the linear programming problem with n inequality constraints can be solved on a probabilistic CRCW PRAM with O(n) processors almost surely in constant time. The algorithm...
A Logic for Reasoning about Probabilities (1990)
Ronald Fagin, Joseph Y. Halpern, Nimrod Megiddo
: We consider a language for reasoning about probability which allows us to make statements such as "the probability of E 1 is less than 1=3" and "the probability of E 1 is at least...
A Logic for Reasoning about Probabilities (1990)
Ronald Fagin, Joseph Y. Halpern, Nimrod Megiddo
: We consider a language for reasoning about probability which allows us to make statements such as "the probability of E 1 is less than 1=3" and "the probability of E 1 is at least...
On the complexity of some geometric problems in unbounded dimension (1990)
This paper examines the complexity of several geometric problems due to un-bounded dimension. The problems considered are: (i) minimum cover of points by unit cubes, (ii) minimum cover of points by...
On probabilistic machines, bounded rationality, and average-case complexity (1989)
ABSTRACT. The analogs of pure, mixed and behavior strategies in the context of algorithms are studied. It is shown that probabilistic machines are more powerful than probability distributions over...
A Note on Total Functions, Existence Theorems, and Computational Complexity (1989)
Nimrod Megiddo, Christos H. Papadimitriou
. Nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist form an interesting complexity class between P and NP. We show that this class, which we...
Homotopy Continuation Methods for Nonlinear Complementarity Problems (1989)
Masakazu Kojima, Nimrod Megiddo, Toshihito Noma
. A complementarity problem with a continuous mapping f from the n-dimensional Euclidean space R n into itself can be written as the system of equations F (x; y) = 0 and (x; y) 0: Here F is the...
On Probabilistic Machines, Bounded Rationality and Average-Case Complexity (1989)
. The analogs of pure, mixed and behavior strategies in the context of algorithms are studied. It is shown that probabilistic machines are more powerful than probability distributions over...
On Computable Beliefs Of Rational Machines (1989)
. Traditional decision theory has assumed that agents have complete, consistent and readily available beliefs and preferences. Obviously, even if an expert system has complete and consistent beliefs,...
Exact Computation of Optimal Inventory Policies over an Unbounded Horizon (1989)
. An inventory scheduling model with forbidden time intervals is analyzed. The objective is to minimize the long-term average cost per time unit. Unlike most of the literature on inventory theory, no...
On Computable Beliefs of Rational Machines (1989)
Traditional decision theory has assumed that agents havecomplete, consistent and readily available beliefs and preferences. Obviously,even if an expert system has complete and consistent beliefs, it...
Exact Computation of Optimal Inventory Policies over an Unbounded Horizon (1989)
An inventory scheduling model with forbidden time intervals is analyzed. The objective is to minimize the long-term average cost per time unit.
Nimrod Megiddo, Christos H. Papadimitriou, Communicated M. Nivat
On total functions, existence theorems and computational complexity
North-Holland Approximation algorithms for hitting (1989)
Hassin, R. and N. Megiddo, Approximation algorithms for hitting objects with straight lines, Discrete Applied Mathematics 30 (1991) 29-42. In the hitting set problem one is given m subsets of a...
A Note on Total Functions, Existence Theorems, and Computational Complexity (1989)
Nimrod Megiddo, Christos H. Papadimitriou
Nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist form an interesting complexity class between P and NP.Weshow that this class,...
A Note on the Complexity of P-Matrix LCP and Computing an Equilibrium (1988)
Abstract. It is proved that if it is NP-hard to solve the linear complementarity problemwith P-matrix or to compute a Nash-equilibrium point in a 2-player game, then NP = coNP. 1.
On the complexity of polyhedral separability (1988)
Abstract. It is NP-complete to recognize whether two sets of points in general space can be separated by twohyperplanes. It is NP-complete to recognize whether two sets of points in the plane can be...
On The Complexity Of Polyhedral Separability (1988)
. It is NP-complete to recognize whether two sets of points in general space can be separated by two hyperplanes. It is NP-complete to recognize whether two sets of points in the plane can be...
On the epsilon-perturbation Method for Avoiding Degeneracy (1988)
Nimrod Megiddo, R. Chandrasekaran
. Although it is NP-complete to decide whether a linear programming problemis degenerate, the ffl-perturbation method can be used to reduce in polynomial time any linear programming problemwith...
A Note on the ComplexityofP-Matrix LCP and Computing (1988)
An Equilibrium Nimrod, Nimrod Megiddo
It is proved that if it is NP-hard to solve the linear complementarity problemwith P-matrix or to compute a Nash-equilibrium point in a 2-player game, then NP = coNP.
On Finding A Minimum Dominating Set In A Tournament (1987)
. The problem of finding a minimum dominating set in a tournament can be solved in njO(log n) time. It is shown that if this problem has a polynomialtime algorithm then for every constant C, there is...
On Finding a Minimum Dominating Set in a Tournament (1987)
The problem of finding a minimum dominating set in a tournament can be solved in njO(log n) time. It is shown that if this problem has a polynomialtime algorithm then for every constant C, there is...
Boundary Behavior Of Interior Point Algorithms In Linear Programming (1986)
. This paper studies the boundary behavior of some interior point algorithms for linear programming. The algorithms considered are Karmarkar's projective rescaling algorithm, the linear...
Ma Research Nimrod, Nimrod Megiddo, Nimrod Megiddo, Nimrod Hlegiddo
The concept of bounded rationality is not well-defined. Several aspects of bounded rationality are discussed. Two different kinds of bounded rationality are distinguished. First, rationality may be...
Computing circular separability (1986)
Nimrod Megiddo, Nimrod Megiddo, S. Rao Kosaraju, S. Rao Kosaraju, S. Rao Kosaraju
This repat has been submitted for publication outside of IBM and will probably be copyrighted il accepted for publication. It has been issued as a Research Report fa early d~ssemination of its...
On play by means of computing machines (1986)
J. Y. Halpern, Morgan Kaufmann Publishers, Nimrod Megiddo, Nimrod Megiddo, Nimrod Megiddo, Avi Wigderson, ...
This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its...
North-Holland SHORT COMMUNICATION A NOTE ON DEGENERACY IN LINEAR PROGRAMMING (1985)
We show that the problem of exiting a degenerate vertex is as hard as the general linear programming problem. More precisely, every linear programming problem can easily be reduced to one where the...
Lemke's algorithm for the linear complementarity problem follows a ray which leads from a certain fixed point (traditionally, the point (1,..., I)~) to the point given in the problem. The...
Linear programming in linear time when the dimension is fixed (1984)
Abstract. It is demonstrated that the linear programming problem in d variables and n constraints can be solved in O(n) time when d is fixed. This bound follows from a multidimensional search...
In this paper we analyze the average number of steps performed by the self-dual simplex algorithm for linear programming, under the probabilistic model of spherical symmetry. The model was proposed...
Applying parallel computation algorithms in the design of serial algorithms (1983)
Abstract. The goal of this paper is to point out that analyses of parallelism in computational problems have practical implications even when multiprocessor machines are not available. This is true...
Applying parallel computation algorithms in the design of serial algorithms (1983)
Abstract. The goal of this paper is to point out that analyses of parallelism m computational problems have practical implications even when mult~processor machines are not available. This is true...
Nimrod Megiddo, Communicated M. Nivat
Abstract. It is proved that there exist encoding schemes which are arbitrarily as efficient as the binary encoding (in terms of compactness and arithmetic operations), with respect to which...
flying objects*
O North-Holland Publishing Company AN INTERGENERATIONAL CAKE EATING GAME (1979)
Morton I. Kamien, Nimrod Megiddo
A game having a simple recursive structure is given. It consists of dividing a fixed stock of a resource among infindely many future generations. An equilibrium solution consists of arrang-ing the...
Printed in USA. COMBINATORIAL OPTIMIZATION WITH RATIONAL OBJECTIVE FUNCTIONS* (1979)
Let A be the problem of minimizing clxl +... + c,x, subject to certain constraints on x = (x,,..., x,), and let B be the problem of minimizing (a, + a,xl +... + o,,x,)/(b, + b,x, +... + b,x,) subject...
@ North-Holland Publishing Company CYCLIC ORDERING IS NP-COMPLETE (1977)
Zvi Galil, Nimrod Megiddo, Z. Galil, N. Megiddo
Abstract. The cyclic ordering problem is to recognize whether a collection of cyclically ordered triples of elements of a set T is derived from an arrangement of all the elements of T on a circle....
Nimrod Megiddo, Nimrod Megiddo
Given f: R: + R", a feasible solution is an x E R: such that f(x) E R:. A complementary solution is a feasible solution x such that xT- f (x) = 0. The mapping f is monotone [4] if (x- Y)~....
@ North-Holland Publishing Company MIXTURES OF ORDER MATRICES AND GENERALIZED ORDER MATRICES (1976)
This paper deals with matrix representations of linear orders, mixtures of order matrices and the non-integral solutions of the linear systems defining them. 1.
Nimrod Megiddo, Nimrod Megiddo
This paper generalizes the answers that were given by R.W. Cottle to questions that were originally raised by G. Maier. Essentially, we give necessary and sufficient conditions for some notions of...
Nimrod Megiddo, Masakazu Kojima, Nimrod Megiddo, Masakazu Kojima
A complementarity problem is said to be globally uniquely solvable (GUS) if it has a unique solution, and this property will not change, even if any constant term is added to the mapping generating...
North-Holland Publishing Company ON THE PARAMETRIC NONLINEAR COMPLEMENTARITY PROBLEM* (1975)
A parametrized version of the nonlinear complementarity problem is formulated. The existence of a continuation of a solution is investigated and sufficient and necessary con-ditions for the...
The concept of an optimal flow in a multiple source, multiple sink network is defined. It generalizes maximal flow in a single source, single sink network. An existence proof and an algo-rithm are...
Efficient Coalition Detection in Traitor Tracing (1970)
Hongxia Jin, Jeffery Lotspiech, Nimrod Megiddo
In this paper we study the traitor tracing problem for re-broadcasting attack. In this attack, instead of building a pirate clone device (or program) based on their secret keys and sell the clone,...
An Interior Point Potential Reduction Algorithm for the Linear Complementarity Problem
Masakazu Kojima, Nimrod Megiddo, Yinyu Ye
. The linear complementarity problem (LCP) can be viewed as the problem of minimizing x T y subject to y = Mx + q and x; y 0. We are interested in finding a point with x T y ! ffl for a given ffl ?...
Masakazu Kojima, Nimrod Megiddo
. Smale proposed a framework for applying Newton's method to the linear programming problem. It is shown that his method is closely related to recent interior point methods, in the sense that it...