All-norm approximation algorithms

DOI10.1016/J.JALGOR.2004.02.003MaRDI QIDQ4815768zbMATH OpenOpenAlexFDO

Authors Leah Epstein, Yossi Richter, Gerhard J. Woeginger, Yossi Azar

Publication date 8 September 2004

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jalgor.2004.02.003

zbMATH Keywords

optimizationscheduling

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• All-Norm Approximation Algorithms
• All-norms and all-\(L_p\)-norms approximation algorithms
• On a class of algorithms for total approximation
• scientific article; zbMATH DE number 1264429
• scientific article; zbMATH DE number 1330032
• Approximation algorithms
• scientific article; zbMATH DE number 3953483
• Approximation algorithms for minimum norm and ordered optimization problems
• scientific article; zbMATH DE number 4215407
• scientific article; zbMATH DE number 503081

Cited in

(21)

• Fair online load balancing
• Simpler and Better Algorithms for Minimum-Norm Load Balancing
• Maximum bipartite flow in networks with adaptive channel width
• Approximate strong equilibria in job scheduling games with two uniformly related machines
• Optimal location with equitable loads
• Price-based protocols for fair resource allocation, convergence time analysis and extension to Leontief utilities
• Improved bounds for distributed load balancing
• All-Norm Approximation Algorithms
• Surrogate optimization for \(p\)-norms
• Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
• Non-clairvoyantly scheduling to minimize convex functions
• An efficient polynomial time approximation scheme for load balancing on uniformly related machines
• Energy-efficient algorithms for non-preemptive speed-scaling
• scientific article; zbMATH DE number 7525465 (Why is no real title available?)
• A unified approach to truthful scheduling on related machines
• All-norms and all-\(L_p\)-norms approximation algorithms
• 2-approximation algorithm for a generalization of scheduling on unrelated parallel machines
• Online scheduling with general cost functions
• Simultaneous approximation of multi-criteria submodular function maximization
• Algorithm Theory - SWAT 2004
• Truthful mechanism design via correlated tree rounding

This page was built for publication: All-norm approximation algorithms

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