NDLI: Approximation Algorithms for Minimum-Time Broadcast

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

Approximation Algorithms for Minimum-Time Broadcast

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Kortsarz, Guy Peleg, David
Copyright Year	1995
Abstract	This paper deals with the problem of broadcasting in minimum time in the telephone and message-passing models. Approximation algorithms are developed for arbitrary graphs as well as for several restricted graph classes.In particular, an $O( \sqrt{n} )$-additive approximation algorithm is given for broadcasting in general graphs, and an $O( \log n/\log \log n )$ (multiplicative) ratio approximation is given for broadcasting in the open-path model. This also results in an algorithm for broadcasting on random graphs (in the telephone and message-passing models) that yields an $O( \log n/\log \log n )$ approximation with high probability.In addition, the paper presents a broadcast algorithm for graph families with small separators (such as chordal, k-outerplanar, bounded-face planar, and series-parallel graphs), with approximation ratio proportional to the separator size times $\log n$. Finally, an efficient approximation algorithm is presented for the class of graphs representable as trees of cliques.
Starting Page	401
Ending Page	427
Page Count	27
File Format	PDF
ISSN	08954801
DOI	10.1137/S0895480193245923
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	3
Volume Number	8
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-08-01
Access Restriction	Subscribed
Subject Keyword	broadcast approximation Analysis of algorithms and problem complexity Graph algorithms Scheduling theory, deterministic Combinatorial optimization
Content Type	Text
Resource Type	Article
Subject	Mathematics

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

Improved Approximation Algorithms for Broadcast Scheduling

General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time

A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling

Fast Algorithms for Bipartite Network Flow

Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs

Improved Approximation Algorithms for Shop Scheduling Problems

Single Machine Scheduling with Release Dates

The Minimum All-Ones Problem for Trees

Approximation Techniques for Average Completion Time Scheduling

Approximation Algorithms for Minimum-Time Broadcast

Similar Documents

Improved Approximation Algorithms for Broadcast Scheduling

General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time

A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling

Fast Algorithms for Bipartite Network Flow

Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs

Improved Approximation Algorithms for Shop Scheduling Problems

Single Machine Scheduling with Release Dates

The Minimum All-Ones Problem for Trees

Approximation Techniques for Average Completion Time Scheduling

Approximation Algorithms for Minimum-Time Broadcast