MSc Thesis Proposal Announcement of Patrick Devaney:"Approximating Average Bounded-Angle Minimum Spanning Trees"

 

Date: Wednesday November 2nd, 2022 

Time:  10:00am-11:30am 

Location: Lambton Tower, Room 3105 

Reminder: Two-part attendance required: Part I (Scan the QR code, fill in online form) and Part II (sign in sheet). *Make sure you are in the room at least 5-10 minutes BEFORE the presentation starts – once the presentation has begun, latecomers will not be admitted.

 

Motivated by the problem of orienting directional antennas in wireless communication networks, we study average bounded-angle minimum spanning trees. Let P be a set of points in the plane and let α be an angle. An α-spanning tree (α-ST) of P is a spanning tree of the complete Euclidean graph induced by P with the restriction that all edges incident to each point p in P lie in a wedge of angle α with apex p. An α-minimum spanning tree (α-MST) of P is an α-ST with minimum total edge length.
An average-α-spanning tree (denoted by avg-α-ST) is a spanning tree with the relaxed condition that incident edges to all points lie in wedges with average angle α. An average-α-minimum spanning tree (avg-α-MST) is an α-ST with minimum total edge length. We focus on α = 2π/3. Let A(2π/3) be the smallest ratio of the length of the 2π/3-MST to the length of the standard MST, over all sets of points in the plane. Biniaz, Bose, Lubiw, and Maheshwari (Algorithmica 2022) showed that 4/3 ≤ A (2π/3) ≤ 3/2. We improve the upper bound and show that A(2π/3) ≤ 13/9. We further examine other values of α. 

 

Keywords: minimum spanning tree (MST), bounded angle MST, approximation algorithm, wireless communication networks, antennas, Euclidean graph

 

Internal Reader: Dr. Asish Mukhopadhyay            

External Reader: Dr. Adrian Zahariuc       

Advisor: Dr. Ahmad Biniaz  

Co-Advisor: Dr. Prosenjit Bose