Simultaneously load balancing for every p-norm, with reassignments

DOI10.4230/LIPIcs.ITCS.2017.51zbMath1402.68196OpenAlexW2775657627MaRDI QIDQ4638106

Seth Pettie, Aaron Bernstein, Ely Porat, Tsvi Kopelowitz, Clifford Stein

Publication date: 3 May 2018

Full work available at URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.51

zbMATH Keywords

graph orientationonline matchingminimizing the \(p\)-norm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20) Online algorithms; streaming algorithms (68W27)

Related Items (1)

Online load balancing with general reassignment cost

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Adjacency queries in dynamic sparse graphs
• Planar orientations with low out-degree and compaction of adjacency matrices
• On-line load balancing and network flow
• A Dynamic Data Structure for Counting Subgraphs in Sparse Graphs
• All maximal independent sets and dynamic dominance for sparse graphs
• Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries
• Oracles for bounded-length shortest paths in planar graphs
• Robust Algorithms for Preemptive Scheduling
• Online Scheduling with Bounded Migration
• Combining fairness with throughput
• Dynamic Set Intersection
• A Robust PTAS for Machine Covering and Packing
• Arboricity and Subgraph Listing Algorithms
• Dynamic Steiner Tree Problem
• Color-coding
• Higher Lower Bounds from the 3SUM Conjecture
• Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap
• Improved Bounds for the Online Scheduling Problem
• Load Balancing for Response Time
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
• Egalitarian Graph Orientations
• Maintaining Assignments Online: Matching, Scheduling, and Flows
• The power of deferral
• The Power of Recourse for Online MST and TSP
• Fairness in routing and load balancing

This page was built for publication: Simultaneously load balancing for every p-norm, with reassignments