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

 

Date: Tuesday April 25th, 2023

Time:  2:00pm – 3:30pm

Location: Essex Hall, Room 105

 

Reminders: 1. Two-part attendance mandatory (sign-in sheet, QR Code) 2. Arrive 5-10 minutes prior to event starting - LATECOMERS WILL NOT BE ADMITTED. Note that due to demand, if the room has reached capacity, even if you are "early" admission is not guaranteed. 3. Please be respectful of the presenter by NOT knocking on the door for admittance once the door has been closed whether the presentation has begun or not (If the room is at capacity, overflow is not permitted (ie. sitting on floors) as this is a violation of the Fire Safety code). 4. Be respectful of the decision of the advisor/host of the event if you are not given admittance. The School of Computer Science has numerous events occurring soon.

 

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 first focus on α = 2π/3. Let A(α) be the smallest ratio of the length of the avg-α-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 then generalize the lower bound argument of Biniaz et al. (Algorithmica 2022) for A(2π/3) to a formula giving a lower bound on A(α) for any α ≤π. We further show how to modify the algorithm of Biniaz et al. (Algorithmica 2022) for the avg-2π/3-MST to compute the avg-π-MST, and show that A(π) = 1. Finally, we present an algorithm to compute the avg-π/2-MST, and show that 3/2 ≤ A(π/2) ≤4.

 

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, Dr. Prosenjit Bose

Chair: Dr. Jessica Chen