Physical Sciences and Mathematics Commons^™

Some Combinational Optimization Problems On Radio Network Communication And Machine Scheduling, Xin Wang

Dissertations

The combinatorial optimization problems coming from two areas are studied in this dissertation: network communication and machine scheduling.

In the network communication area, the complexity of distributed broadcasting and distributed gossiping is studied in the setting of random networks. Two different models are considered: one is random geometric networks, the main model used to study properties of sensor and ad-hoc networks, where ri points are randomly placed in a unit square and two points are connected by an edge if they are at most a certain fixed distance r from each other. The other model is the so-called line-of-sight networks, …