LCS Technical Memos (1974 - 2003): Recent submissions

Now showing items 346-348 of 486

    • Worst-case and Probabilistic Analysis of a Geometric Location Problem 

      Papadimitriou, Christos H. (1980-02)
      We consider the problem of choosing K "medians" among n points on the Euclidean plane such that the sum of the distances from each of the n points to its closest median is minimized. We show that this problem is NP-complete. ...

    • On the Complexity of Integer Programming 

      Papadimitriou, Christos H. (1980-02)
      We give a simple proof that integer programming is in NP. Our proof also establishes that there is a pseudopolynomial time algorithm for integer programming with any (fixed) number of constraints.

    • Reversible Computing 

      Toffoli, Tommaso (1980-02)
      The theory of reversible computing is based on invertible primitives and composition rules that preserve invertibility. With these constraints, one can still satisfactorily deal with both functional and structural aspects ...