The complexity of optimizing atomic congestion

DOI10.1016/J.ARTINT.2024.104241MaRDI QIDQ6665726zbMATH OpenFDO

Authors Cornelius Brand, Robert Ganian, Subrahmanyam Kalyanasundaram, Fionn Mc Inerney

Publication date 17 January 2025

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.ARTINT.2024.104241

zbMATH Keywords

atomic congestion gamesparameterized complexityroutingslim treecut widthsystem optimum

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Potential and congestion games (91A14) Games involving graphs (91A43)

Recommendations

• Computing the price of anarchy in atomic network congestion games (invited talk)
• Atomic Routing Games on Maximum Congestion
• Atomic routing games on maximum congestion
• The complexity of welfare maximization in congestion games
• The minimum tollbooth problem in atomic network congestion games with unsplittable flows

Cites work

• A class of games possessing pure-strategy Nash equilibria
• Algorithmic applications of tree-cut width
• Data Reduction for Maximum Matching on Real-World Graphs
• Delay-robust routes in temporal graphs
• Digraph measures: Kelly decompositions, games, and orderings
• Directed tree-width
• Fundamentals of parameterized complexity
• Graph minors. II. Algorithmic aspects of tree-width
• Graph searching and a min-max theorem for tree-width
• scientific article; zbMATH DE number 7278041 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Immersions in highly edge connected graphs
• Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
• Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
• New algorithms for maximum disjoint paths based on tree-likeness
• Parameterized algorithms
• Parameterized complexity results for exact Bayesian network structure learning
• Slim tree-cut width
• Sparsity. Graphs, structures, and algorithms
• The complexity landscape of decompositional parameters for ILP
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• The complexity of binary matrix completion under diameter constraints
• The complexity of pure Nash equilibria
• The dag-width of directed graphs
• The maximum edge-disjoint paths problem in bidirected trees
• The power of cut-based parameters for computing edge-disjoint paths
• The price of anarchy of finite congestion games
• The price of routing unsplittable flow
• XSAT and NAE-SAT of linear CNF classes

This page was built for publication: The complexity of optimizing atomic congestion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6665726)