Concepedia

Sublinear-time Optimization

Sublinear-Time Optimization is an algorithmic framework that belongs to the class of optimization methods and is distinguished by its ability to compute approximate solutions to optimization problems in time strictly sublinear in the input size, typically by exploiting sampling, sketching, or local search strategies.

60

Publications

4.6K

Citations

133

Authors

86

Institutions

Publications per year

2017–2026

14

Parents

Publications

60

Beyond sliding windows: Object localization by efficient subwindow search

Christoph H. Lampert, Matthew B. Blaschko, Thomas Hofmann · 2008 · 692 citations

, , +16

Efficient Subwindow Search: A Branch and Bound Framework for Object Localization

Christoph H. Lampert, Matthew B. Blaschko, Thomas Hofmann · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2009 · 348 citations · Full text

, , +16

Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality

Piotr Indyk · 1998 · 319 citations

, , +17

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)

Anshumali Shrivastava, Ping Li · arXiv (Cornell University) · 2014 · 257 citations · Full text

, , +16

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

Niv Buchbinder, Moran Feldman, Joseph Naor et al. · 2012 · 237 citations

, , +15

1–5 of 60

Authors

133

  1. EH
    Elad Hazan

    Princeton University, United States

    5 publications · 204 citations

    5

    h-index

  2. PI
    Piotr Indyk

    Massachusetts Institute of Technology, United States

    3 publications · 340 citations

    3

    h-index

  3. RR
    Ronitt Rubinfeld

    Massachusetts Institute of Technology, United States

    3 publications · 107 citations

    3

    h-index

  4. RS
    Roy Schwartz

    Technion – Israel Institute of Technology, Israel

    2 publications · 467 citations

    2

    h-index

  5. ZW
    Zhuang Wang

    Sichuan University, China

    2 publications · 43 citations

    2

    h-index

1–5 of 133

Institutions

86

  1. Technion – Israel Institute of Technology

    Haifa, Israel

    6 h-index

    10 publications

    764 citations

  2. Google (United States)

    Mountain View, United States

    4 h-index

    5 publications

    1.3K citations

  3. University of Michigan

    Ann Arbor, United States

    3 h-index

    7 publications

    501 citations

  4. Rutgers, The State University of New Jersey

    New Brunswick, United States

    3 h-index

    3 publications

    614 citations

  5. Stanford University

    Stanford, United States

    3 h-index

    3 publications

    342 citations

  6. Carnegie Mellon University

    Pittsburgh, United States

    3 h-index

    3 publications

    188 citations

  7. Tel Aviv University

    Tel Aviv, Israel

    3 h-index

    7 publications

    498 citations

  8. Microsoft (United States)

    Redmond, United States

    3 h-index

    4 publications

    404 citations

1–8 of 86

Venues

  1. SIAM Journal on Computing

    4 publications · 469 citations

    4

    h-index

  2. Algorithmica

    2 publications · 71 citations

    2

    h-index

  3. Neural Information Processing Systems

    Conference · 2 publications · 171 citations

    2

    h-index

  4. IEEE Transactions on Evolutionary Computation

    2 publications · 61 citations

    2

    h-index

  5. arXiv (Cornell University)

    Repository · 2 publications · 358 citations

    2

    h-index

1–5