Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach

No abstract is available for this paper.

• Publication year

  2014

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2014-01-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/1.9781611973402.5
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximating Bin Packing within O(log OPT * Log Log OPT) Bins

  2013cited by this paper
• Constructive Discrepancy Minimization by Walking on the Edges

  2012influential reference
• Beck's Three Permutations Conjecture: A Counterexample and Some Consequences

  2012influential reference
• Tight hardness results for minimizing discrepancy

  2011cited by this paper
• An online scalable algorithm for average flow time in broadcast scheduling

  2010cited by this paper
• Better Scalable Algorithms for Broadcast Scheduling

  2010cited by this paper
• Constructive Algorithms for Discrepancy Minimization

  2010cited by this paper
• Longest Wait First for Broadcast Scheduling [Extended Abstract]

  2009cited by this paper
• Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling

  2009cited by this paper
• Broadcast scheduling: algorithms and complexity

  2008cited by this paper
• Scheduling : When Fairness is

  2007cited by this paper
• A robust maximum completion time measure for scheduling

  2006cited by this paper
• Improved approximation algorithms for broadcast scheduling

  2006influential reference
• Pull-based data broadcast with dependencies: be fair to users, not to items

  2006cited by this paper
• Approximating the average response time in broadcast scheduling

  2005influential reference
• Handbook of Scheduling: Algorithms, Models, and Performance Analysis

  2004cited by this paper
• A maiden analysis of longest wait first

  2004cited by this paper
• Equivalence of two linear programming relaxations for broadcast scheduling

  2004cited by this paper
• Paths, trees, and minimum latency tours

  2003cited by this paper
• Dependent rounding in bipartite graphs

  2002cited by this paper
• NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow

  2002influential reference
• Throughput maximization of real-time scheduling with batching

  2002cited by this paper
• Algorithms for Minimizing Response Time in Broadcast Scheduling

  2002cited by this paper
• Scheduling Broadcasts in Wireless Networks

  2000cited by this paper
• Minimizing maximum response time in scheduling broadcasts

  2000cited by this paper
• The Discrepancy Method

  1998cited by this paper
• An improved approximation ratio for the minimum latency problem

  1996cited by this paper
• The minimum latency problem

  1994cited by this paper
• Six standard deviations suffice

  1985cited by this paper
• An efficient approximation scheme for the one-dimensional bin-packing problem

  1982cited by this paper

• Asymptotic Bounds and Online Algorithms for Average-Case Matrix Discrepancy

  2024cites this paper
• Optimal Online Discrepancy Minimization

  2023cites this paper
• Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank

  2022cites this paper
• The online food delivery problem on stars

  2022cites this paper
• Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical

  2022cites this paper
• Flow time scheduling and prefix Beck-Fiala

  2022cites this paper
• A new framework for matrix discrepancy: partial coloring bounds via mirror descent

  2021cites this paper
• Generalised Pattern Matching Revisited

  2020cites this paper
• Flow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Models

  2018cites this paper
• Algorithms for combinatorial discrepancy

  2018cites this paper
• Dynamic priority scheduling of periodic queries in on-demand data dissemination systems

  2017cites this paper
• The Gram-Schmidt walk: a cure for the Banaszczyk blues

  2017cites this paper
• Competitive Algorithms from Competitive Equilibria

  2017cites this paper
• An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound

  2016cites this paper
• Broadcast Scheduling: Minimizing Average Response Time

  2016cites this paper
• Algorithmic discrepancy beyond partial coloring

  2016cites this paper
• Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems

  2016cites this paper
• Minimizing the maximum flow time in batch scheduling

  2016cites this paper
• New Approximations for Broadcast Scheduling via Variants of α-point Rounding

  2015cites this paper
• Design of Scheduling Algorithms Using Game Theoretic Ideas

  2015cites this paper
• Approximation-Friendly Discrepancy Rounding

  2015cites this paper
• Efficient algorithms for discrepancy minimization in convex sets

  2014cites this paper
• Discrepancy Without Partial Colorings

  2014cites this paper
• NEW COMPUTATIONAL ASPECTS OF DISCREPANCY THEORY

  2014cites this paper
• Minimizing Average Response Time in Broadcast Scheduling

  2014cites this paper
• Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints

  2014cites this paper
• New developments in iterated rounding

  2014cites this paper