dimacs logo color

Events

Workshop Details

13th DIMACS Implementation Challenge: Network Flows 2.0

  • Start Date: January 28, 2027
  • End Date: January 29, 2027
  • Event Start Time: 9:00 AM
  • Event End Time: 5:00 PM
  • Organizers: David P. Williamson | Daniel A. Spielman | Giuseppe Italiano | Andrew V. Goldberg | Loukas Georgiadis | Tamra Carpenter | Clifford Stein
  • Location:

    Lehigh University

  • The PDF documents linked on this page, are no longer maintained and may not meet accessibility standards. To request an accessible version of any content, please contact us.

    Implementation Challenges trace back to the early years of DIMACS and to the vision of David S. Johnson to use experimentation as a companion to theory to gain more holistic perspective on the performance of algorithms. The over-arching purpose of a Challenge is to assess the practical performance of algorithms for a particular problem class, while fostering interactions that transfer ideas between research areas related to algorithms, data structures, implementation, and applications. This 13th DIMACS Implementation Challenge will revisit the topic of the inaugural Implementation Challenge on Network Flows.

    The First Challenge greatly reduced the gap between theory and practice and raised standards for experimental work in the area. In the intervening decades, network flow algorithms evolved and new applications of network flows emerged. Many original benchmark instances are too easy for the improved implementations. Theoretical progress has been especially impressive, leading to near-linear algorithms for the minimum-cost flow problem and its special cases. Once again, experimental work is falling behind. The need for updated benchmarks and new algorithm implementations motivates the Network Flows 2.0 Challenge.

    The Challenges focuses on the minimum-cost flow problem and its variants and special cases, including:

    • ˆ minimum-cost flow problem
    • ˆ transportation problem
    • ˆ assignment problem
    • ˆ maximum-flow problem
    • ˆ bipartite matching problem
    • ˆ global minimum cut problem

    The Challenge Workshop will take place on January 28-29, at Lehigh University in Bethlehem, PA, USA. The workshop immediately follows the 2027 SODA and ALENEX conferences, which will be held in Philadelphia, PA, about 70 miles from Bethlehem.

    For details on how to compete in the Challenge or contribute instances, please visit the Network Flows 2.0 website.

    View Challenge CFP.

  • Network Flows 2.0 is organized in collaboration with DIMACS as a part of Lehigh ISE Optimization Science (LIOS) Program.