Tugce Erkilic , OPTIMIZING THE SERVICE POLICY OF A MOBILE SERVICE PROVIDER THROUGH COMPETITIVE ONLINE SOLUTIONS TO THE 0/1 KNAPSACK PROBLEM WITH DYNAMIC CAPACITY , 2014

  Demand for sustainable and environmentally friendly communication systems with energy efficient transmission schemes has increased eminently in the last decades. Resource allocation problems for energy harvesting networks have been studied and many offline solutions have been proposed. An online problem is examined throughout this thesis. Recent industry efforts to provide Internet service to areas deprived of telecommunications infrastructure have been the main inspiration for the studies conducted here. A mobile Internet service provider, a flying platform in the lower stratosphere empowered by the renewable energy (solar, wind, etc.), is envisioned to provide Internet access to the users as it moves over an area. Throughout its path, the station aims to achieve maximum throughput by responding to the demands of the users while prudently managing its available energy. Given the related background, first, the problem is modelled as a 0/1 knapsack problem. Then, several online heuristics are proposed using threshold policies obtained through various methods applied to the decision problem, including rule-based heuristics. Performances of these policies are compared via competitive ratio analysis with the optimal offline solution, which yield a computationally efficient outcome .