NDLI: NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow

Please wait, while we are loading the content...

Static optimality and dynamic search-optimality in lists and trees

Optimal time-space trade-offs for non-comparison-based sorting

Union-find with deletions

A locality-preserving cache-oblivious dynamic dictionary

Cache oblivious search trees via binary trees of small height

An approximation algorithm for the group Steiner problem

On directed Steiner trees

An 8/13-approximation algorithm for the asymmetric maximum TSP

Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems

An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph

Censorship resistant peer-to-peer content addressable networks

Web caching with request reordering

Improved algorithms for the data placement problem

Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees

Temporary tasks assignment resolved

Dense point sets have sparse Delaunay triangulations: or "…but not too nasty"

Delaunay triangulation programs on surface data

Quality meshing with weighted Delaunay refinement

Linear-size approximate voronoi diagrams

Motorcycle graphs and straight skeletons

Faster approximation schemes for fractional multicommodity flow problems

Flows over time with load-dependent transit times

Improved bounds for the unsplittable flow problem

NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow

How unfair is optimal routing?

Approximation algorithms for grammar-based compression

Improving table compression with combinatorial optimization

Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits

Succinct representations of lcp information and improvements in the compressed suffix arrays

Succinct indexable dictionaries with applications to encoding k-ary trees and multisets

Guessing secrets with inner product questions

Guessing secrets efficiently via list decoding

How to cut a cake almost fairly

The mathematics of playing golf

Computing shortest paths with comparisons and additions

An optimal algorithm for checking regularity: (extended abstract)

Edge dominating and hypomatchable sets

An algorithm for counting maximum weighted independent sets and its applications

Algorithms for quantified Boolean formulas

Balls and bins models with feedback

A note on random 2-SAT with prescribed literal degrees

Mixing time and long paths in graphs

The diameter of a long range percolation graph

Is the internet fractal?

Center and diameter problems in plane triangulations and quadrangulations

Symmetric drawings of triconnected planar graphs

Layout area of the hypercube: (extended abstract)

I/O-optimal algorithms for planar graphs using separators

Polynomial time recognition of P4-structure

Adaptive intersection and t-threshold problems

Separable attributes: a technique for solving the sub matrices character count problem

Tiling groups for Wang tiles

Generating random factored numbers, easily

Tight bounds for worst-case equilibria

Broadcast scheduling: when fairness is fine

Harmonic broadcasting is optimal

Windows scheduling problems for broadcast systems

Scheduling protocols for switches with large envelopes

Covering shapes by ellipses

Slice and dice: a simple, improved approximate tiling recipe

Binary space partitions for line segments with a limited number of directions

Closest-point problems simplified on the RAM

Semi-online maintenance of geometric optima and measures

Generalized clustering

New bounds for multi-dimensional packing

Computer assisted proof of optimal approximability results

MAX CUT in cubic graphs

Approximating minimum unsatisfiability of linear equations

On-line algorithms for the dynamic traveling repair problem

Competitive on-line switching policies

A randomized online algorithm for bandwidth utilization

Caching with expiration times

On-line scheduling of a single machine to minimize total weighted completion time

Hardware-assisted computation of depth contours

The freeze-tag problem: how to wake up a swarm of robots

The wake up and report problem is time-equivalent to the firing squad synchronization problem

Tree exploration with little memory

Efficient proper 2-coloring of almost disjoint hypergraphs

Experimental analysis of simple, distributed vertex coloring algorithms

On semidefinite programming relaxations for graph coloring and vertex cover

Approximating k-cuts via network strength

Reductions in streaming algorithms, with an application to counting triangles in graphs

Sampling from a moving window over streaming data

Maintaining stream statistics over sliding windows: (extended abstract)

Testing satisfiability

Efficient pattern-matching with don't cares

Efficient algorithms for document retrieval problems

The string edit distance matching problem with moves

Simple approximation algorithm for nonoverlapping local alignments

A sub-quadratic sequence alignment algorithm for unrestricted cost matrices

On adaptive deterministic gossiping in ad hoc radio networks

Expansion of product replacement graphs

Explicit constructions of selectors and related combinatorial structures, with applications

Derandomized dimensionality reduction with applications

Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms

Existence theorems, lower bounds and algorithms for scheduling to meet two objectives

Scheduling split intervals

Throughput maximization of real-time scheduling with batching

(Incremental) priority algorithms

Improved algorithms for stretch scheduling

Shape dimension and approximation from samples

Smooth-surface reconstruction in near-linear time

Computing the writhing number of a polygonal knot

Pseudo-line arrangements: duality, algorithms, and applications

On the overlay of envelopes in four dimensions

Preprocessing an undirected planar network to enable fast approximate distance queries

Approximate distance oracles for geometric graphs

Oracles for distances avoiding a link-failure

Roundtrip spanners and roundtrip routing in directed graphs

Light spanners and approximate TSP in weighted graphs with forbidden minors

Capacitated vertex covering with applications

Construction of probe interval models

A new algorithm for protein folding in the HP model

An optimal (expected time) algorithm for minimizing lab costs in DNA sequencing

Approximating minimum quartet inconsistency: (abstract)

Matrix rounding under the Lp-discrepancy measure and its application to digital halftoning

Smoothed analysis of the perceptron algorithm for linear programming

A fully combinatorial algorithm for submodular function minimization

0/1 optimization and 0/1 primal separation are equivalent

Labeling schemes for flow and connectivity

Reachability and distance queries via 2-hop labels

Improved labeling scheme for ancestor queries

A comparison of labeling schemes for ancestor queries

Incentive-compatible online auctions for digital goods

Online algorithms for market clearing

Pricing multicasting in more practical network models

Frugal path mechanisms

an approximation algorithm for minimum-cost vertex-connectivity problems

NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow

Content Provider	ACM Digital Library
Author	Hall, Alexander Erlebach, Thomas
Abstract	We consider the version of broadcast scheduling where a server can transmit one message of a given set at each time-step, answering previously made requests for that message. The goal is to minimize the average response time if the amount of requests is known in advance for each time-step and message. We prove that this problem is NP-hard, thus answering an open question stated by Kalyanasundaram, Pruhs and Velauthapillai (Proceedings of ESA 2000, LNCS 1879, 2000, pp. 290-301). Furthermore, we present an approximation algorithm that is allowed to send several messages at once. Using 6 channels for transmissions, the algorithm achieves an average response time that is at least as good as the optimal solution using one channel. The best previous approximation algorithm achieved ratio 1.5 with 6 channels and reached ratio 1 only in the case where there are as many channels as messages.From the NP-hardness of broadcast scheduling we derive a new inapproximability result of (2-ε, 1) for the (congestion,cost) bicriteria version of the single source unsplittable min-cost flow problem, for arbitrary ε > 0. The result holds even in the often considered case where the maximum demand is less than or equal to the minimum edge capacity (dmax ≤ umin), a case for which an algorithm with ratio (3, 1) was presented by Skutella.
Starting Page	194
Ending Page	202
Page Count	9
File Format	PDF
ISBN	089871513X
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-01-06
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in