Arrow Research search

Author name cluster

Nimrod Megiddo

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

28 papers
2 author rows

Possible papers

28

NeurIPS Conference 2004 Conference Paper

Exploration-Exploitation Tradeoffs for Experts Algorithms in Reactive Environments

  • Daniela Farias
  • Nimrod Megiddo

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 experts more carefully than in oblivious ones. In addition, a more subtle definition of a learnable value of an expert is required. A general exploration-exploitation experts method is presented along with a proper definition of value. The method is shown to asymptotically perform as well as the best available expert. Several variants are analyzed from the viewpoint of the exploration-exploitation tradeoff, including explore-then-exploit, polynomially vanishing exploration, constant-frequency exploration, and constant-size explo- ration phases. Complexity and performance bounds are proven.

PDF Details

NeurIPS Conference 2003 Conference Paper

How to Combine Expert (and Novice) Advice when Actions Impact the Environment?

  • Daniela de Farias
  • Nimrod Megiddo

The so-called “experts algorithms” constitute a methodology for choos- ing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the environment. An experts algorithm has access to a set of strategies (“experts”), each of which may recommend which action to choose. The algorithm learns how to com- bine the recommendations of individual experts so that, in the long run, for any fixed sequence of states of the environment, it does as well as the best expert would have done relative to the same sequence. This method- ology may not be suitable for situations where the evolution of states of the environment depends on past chosen actions, as is usually the case, for example, in a repeated non-zero-sum game. A new experts algorithm is presented and analyzed in the context of re- peated games. It is shown that asymptotically, under certain conditions, it performs as well as the best available expert. This algorithm is quite different from previously proposed experts algorithms. It represents a shift from the paradigms of regret minimization and myopic optimiza- tion to consideration of the long-term effect of a player’s actions on the opponent’s actions or the environment. The importance of this shift is demonstrated by the fact that this algorithm is capable of inducing co- operation in the repeated Prisoner’s Dilemma game, whereas previous experts algorithms converge to the suboptimal non-cooperative play.

PDF Details

TCS Journal 2000 Journal Article

A sublinear parallel algorithm for stable matching

  • Tomás Feder
  • Nimrod Megiddo
  • Serge A. Plotkin

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 matching can be found in O ∗( m ) time by a polynomial number of processors, where m is the total length of preference lists of individuals.

Details DOI

TCS Journal 1998 Journal Article

Using fast matrix multiplication to find basic solutions

  • Peter A. Beling
  • Nimrod Megiddo

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 complexity bounds for this problem admit considerable improvement. Our technique, which is similar in spirit to that used by Vaidya to find the best complexity bounds for linear programming, is based on reducing much of the computation involved to matrix multiplication. Consequently, our complexity bounds in their most general form are a function of the complexity of matrix multiplication. Using the best known algorithm for matrix multiplication, we achieve a running time of O(m 1. 594 n) arithmetic operations for an m × n problem in standard form. Previously, the best bound was O(m 2 n) arithmetic operations.

Details DOI

FOCS Conference 1995 Conference Paper

Improved Algorithms and Analysis for Secretary Problems and Generalizations

  • Miklós 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 rank relative to the ones already seen. Variants of the problem depend on the goal: either maximize the probability of accepting the best k objects, or minimize the expectation of the sum of the ranks (or powers of ranks) of the accepted objects. The problem and its generalizations are at the core of tasks with a large data set, in which it may be impractical to backtrack and select previous choices. Optimal algorithms for the special case of k=1 are well known. Partial solutions for the first variant with general k are also known. In contrast, an explicit solution for the second variant with general k has not been known; even the question of whether or not the expected sum of powers of the ranks of selected items tends to infinity with n has been unresolved. We answer these open questions by obtaining explicit algorithms. For each z/spl ges/1, the resulting expected sum of the zth powers of the ranks of the selected objects is at most k/sup z+1//(z+1)+C(z)/spl middot/k/sup z+0. 5/log k, whereas the best possible value at all is k/sup z+1//(z+1)+O(k/sup z/). Our methods are very intuitive and apply to some generalizations. We also derive a lower bound on the trade-off between the probability of selecting the best object and its expected rank.

Details

STOC Conference 1992 Conference Paper

A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension

  • Miklós Ajtai
  • Nimrod Megiddo

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 time. The parallel time bound is O((log log n ) d ) where d is the number of variables. In the one-dimensional case this bound is optimal.

Details

TCS Journal 1991 Journal Article

On total functions, existence theorems and computational complexity

  • 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 call TFNP, contains a host of important problems, whose membership in P is currently not known. These include, besides factoring, local optimization, Brouwer's fixed points, a computational version of Sperner's Lemma, bimatrix equilibria in games, and linear complementarity for P-matrices.

Details DOI

I&C Journal 1990 Journal Article

A logic for reasoning about probabilities

  • 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 twice the probability of E 2, ” where E 1 and E 2 are arbitrary events. We consider the case where all events are measurable (i. e. , represent measurable sets) and the more general case, which is also of interest in practice, where they may not be measurable. The measurable case is essentially a formalization of (the propositional fragment of) Nilsson's probabilistic logic. As we show elsewhere, the general (nonmeasurable) case corresponds precisely to replacing probability measures by Dempster-Shafer belief functions. In both cases, we provide a complete axiomatization and show that the problem of deciding satisfiability is NP-complete, no worse than that of propositional logic. As a tool for proving our complete axiomatizations, we give a complete axiomatization for reasoning about Boolean combinations of linear inequalities, which is of independent interest. This proof and others make crucial use of results from the theory of linear programming. We then extend the language to allow reasoning about conditional probability and show that the resulting logic is decidable and completely axiomatizable, by making use of the theory of real closed fields.

Details DOI

FOCS Conference 1990 Conference Paper

Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time

  • Noga Alon
  • Nimrod Megiddo

It is shown that, for any fixed dimension d, the linear programming problem with n inequality constraints can be solvent on a probabilistic CRCW PRAM (concurrent-read-concurrent-write parallel random-access machine) with O(n) processors almost surely in constant time. The algorithm always finds the correct solution. With nd/log/sup 2/d processors, the probability that the algorithm will not finish within O(d/sup 2/log/sup 2/d) time tends to zero exponentially with n. >

Details

TCS Journal 1988 Journal Article

On finding a minimum dominating set in a tournament

  • Nimrod Megiddo
  • Uzi Vishkin

The problem of finding a minimum dominating set in a tournament can be solved in n O(log n ) time. It is shown that if this problem has a polynomial-time algorithm, then for every constant C, there is also a polynomial-time algorithm for the satisfiability problem of boolean formulas in conjunctive normal form with m clauses and C log2 m variables. On the other hand, the problem can be reduced in polynomial time to a general satisfiability problem of length L with O(log2 L) variables. Another relation between the satisfiability problem and the minimum dominating set in a tournament says that the former can be solved in 2O(√v) nK time (where v is the number of variables, n is the length of the formula, and K is a constant) if and only if the latter has a polynomial-time algorithm.

Details DOI

TCS Journal 1982 Journal Article

Is binary encoding appropriate for the problem-language relationship?

  • Nimrod Megiddo

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 Khachiyan's algorithm for Linear Programming is exponential. This constitutes an objection to the standard translation of problems into languages via the binary encoding.

Details DOI

FOCS Conference 1982 Conference Paper

Linear-Time Algorithms for Linear Programming in R^3 and Related Problems

  • Nimrod Megiddo

Linear-time for Linear Programming in R2 and R3 are presented. The methods used are applicable for some other problems. For example, a linear-time algorithm is given for the classical problem of finding the smallest circle enclosing n given points in the plane. This disproves a conjecture by Shamos and Hoey that this problem requires Ω(n log n) time. An immediate consequence of the main result is that the problem of linear separability is solvable in linear-time. This corrects an error in Shamos and Hoey's paper, namely, that their O(n log n) algorithm for this problem in the plane was optimal. Also, a linear-time algorithm is given for the problem of finding the weighted center of a tree and algorithms for other common location-theoretic problems are indicated. The results apply also to the problem of convex quadratic programming in three-dimensions. The results have already been extended to higher dimensions and we know that linear programming can be solved in linear-time when the dimension is fixed. This will be reported elsewhere; a preliminary report is available from the author.

Details

FOCS Conference 1981 Conference Paper

Applying Parallel Computation Algorithms in the Design of Serial Algorithms

  • Nimrod Megiddo

The goal of this paper is to point out that analyses of parallelism in computational problems have practical implications even when multi-processor machines are not available. This is true because, in many cases, a good parallel algorithm for one problem may turn out to be useful for designing an efficient serial algorithm for another problem. A unified framework for cases like this is presented. Particular cases, which are discussed in this paper, provide motivation for examining parallelism in problems like sorting, selection, minimum-spanning-tree, shortest route, maxflow, matrix multiplication, as well as scheduling and locational problems.

Details

FOCS Conference 1981 Conference Paper

The Complexity of Searching a Graph (Preliminary Version)

  • Nimrod Megiddo
  • S. Louis Hakimi
  • M. R. Garey
  • David S. Johnson 0001
  • Christos H. Papadimitriou

T. Parsons proposed and partially analyzed the following pursuit-evasion problem on graphs: A team of searchers traverse the edges of a graph G in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number s(G) of searchers that will suffice for guaranteeing capture of the fugitive? We show that determining whether s(G) ≤ K, for a given integer K, is NP-hard for general graphs but can be solved in linear time for trees. We also provide a structural characterization of those graphs with s(G) ≤ K for K = 1, 2, 3.

Details

TCS Journal 1977 Journal Article

Cyclic ordering is NP-complete

  • Zvi Galil
  • Nimrod Megiddo

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. This problem is shown to be NP-complete.

Details DOI
v2026.09.13