Concepedia

Network Design Approximation

Network Design Approximation is a computational framework within algorithmic optimization that specifically addresses the construction of cost-effective network topologies under constraints by providing provably near-optimal solutions to NP-hard problems in graph connectivity, edge selection, and infrastructure planning.

153

Publications

9.2K

Citations

234

Authors

122

Institutions

Publications per year

2017–2026

14

Parents

Publications

153

A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem

Kamal Jain · COMBINATORICA · 2001 · 560 citations

, , +14

When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Ajit Agrawal, Philip N. Klein, R. Ravi · SIAM Journal on Computing · 1995 · 420 citations

, , +11

The complexity of the network design problem

David Johnson, Jan Karel Lenstra, A. H. G. Rinnooy Kan · Networks · 1978 · 400 citations · Full text

, , +15

Equilibrium Decomposed Optimization: A Heuristic for the Continuous Equilibrium Network Design Problem

Chaisak Suwansirikul, Terry L. Friesz, Roger L. Tobin · Transportation Science · 1987 · 339 citations

, , +16

A unified approach to approximation algorithms for bottleneck problems

Dorit S. Hochbaum, David B. Shmoys · Journal of the ACM · 1986 · 327 citations · Full text

, , +16

1–5 of 153

Authors

234

  1. RR
    R. Ravi

    Carnegie Mellon University, United States

    16 publications · 1.3K citations

    15

    h-index

  2. AG
    Anupam Gupta

    Carnegie Mellon University, United States

    11 publications · 514 citations

    11

    h-index

  3. CC
    Chandra Chekuri

    University of Illinois Urbana-Champaign, United States

    10 publications · 440 citations

    10

    h-index

  4. JC
    Joseph Cheriyan

    University of Waterloo, Canada

    8 publications · 332 citations

    8

    h-index

  5. SK
    Sanjeev Khanna

    University of Pennsylvania, United States

    7 publications · 311 citations

    7

    h-index

1–5 of 234

Institutions

122

  1. Carnegie Mellon University

    Pittsburgh, United States

    19 h-index

    38 publications

    2.2K citations

  2. Cornell University

    Ithaca, United States

    10 h-index

    20 publications

    2.1K citations

  3. University of Waterloo

    Waterloo, Canada

    9 h-index

    9 publications

    373 citations

  4. Stanford University

    Stanford, United States

    8 h-index

    19 publications

    2.1K citations

  5. University of Pennsylvania

    Philadelphia, United States

    7 h-index

    10 publications

    1.4K citations

  6. McGill University

    Montreal, Canada

    7 h-index

    11 publications

    196 citations

  7. Technion – Israel Institute of Technology

    Haifa, Israel

    7 h-index

    11 publications

    347 citations

  8. University of California, Berkeley

    Berkeley, United States

    7 h-index

    13 publications

    1.5K citations

1–8 of 122

Venues

  1. SIAM Journal on Computing

    12 publications · 902 citations

    12

    h-index

  2. Algorithmica

    6 publications · 324 citations

    6

    h-index

  3. Networks

    5 publications · 572 citations

    5

    h-index

  4. ACM Transactions on Algorithms

    TALG · 5 publications · 168 citations

    5

    h-index

  5. Transportation Research Part B Methodological

    4 publications · 474 citations

    4

    h-index

1–5