George Karakostas

Selfish routing in the presence of side constraints

  • George Karakostas
  • Stavros Kolliopoulos
    • Categories Network Optimization Tags ,

    The natural approach for describing network flow problems is to introduce side constraints that capture restrictions of a logical or technological nature, e.g., capacity constraints. We study the traffic equilibria arising from selfish routing of individual users in networks with side constraints. We examine first the case of linear latency functions. Under very general assumptions … Read more

    Faster Approximation Schemes for Fractional Multicommodity Flow Problems

  • George Karakostas
    • Categories Network Optimization Tags

    We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of minimal dependency on the number of commodities k. We show that by modifying the algorithms by Garg & Konemann and Fleischer we can reduce their running time to a logarithmic dependence on k, and essentially match the running time … Read more