Homework 2 Greedy Algorithms Solution

You are consulting for a trucking company that does a large amount of business shipping packages between New York and Boston. The volume is high enough that they have to send a number of trucks each day



between the two locations. Trucks have a xed limit W on the maximum amount of weight they are allowed to carry. Boxes arrive at the New York station one by one, and each package i has a weight wi. The trucking station is quite small, so at most one truck can be at the station at any time. Company policy requires that boxes are shipped in the order they arrive; otherwise, a customer might get upset upon seeing a box that arrived after his make it to Boston faster. At the moment, the company is using a simple greedy algorithm for packing: they pack boxes in the order they arrive, and whenever the next box does not t, they send the truck on its way.




But they wonder if they might be using too many trucks, and they want your opinion on whether the situation can be improved. Here is how they are thinking. Maybe one could decrease the number of trucks needed by sometimes sending o a truck that was less full, and in this way allow the next few trucks to be better packed.




Prove that, for a given set of boxes with speci ed weights, the greedy algorithm currently in use actually minimizes the number of trucks that are needed. Your proof should follow the type of analysis we used for the Interval Scheduling Problem: it should establish the optimality of this greedy packing algorithm by identifying a measure under which it "stays ahead" of all other solutions.
















Let's consider a long, quiet country road with houses scattered very sparsely along it. (We can picture the road as a long line segment, with an eastern endpoint and a western endpoint.) Further, let's suppose that despite the bucolic setting, the residents of all these houses are avid cell phone users. You want to place cell phone base stations at certain points along the road, so that every house is within four miles of one of the base stations.



Give an e cient algorithm that achieves this goal, using as few base stations as possible.













Let G = (V; E) be an (undirected) graph with costs ce = 0 on the edges e 2 E. Assume you are given a minimum-cost spanning tree T in G. Now assume that a new edge is added to G, connecting two nodes v; w 2 V with cost c.

Give an e cient algorithm to test if T remains the minimum-cost spanning tree with the new edge



added to G (but not to the tree T ). Make your algorithm run in time O(jEj). Can you do it inO(jV j) time? Please note any assumptions you make about what data structure is used to represent the tree T and the graph G.




Suppose T is no longer the minimum-cost spanning tree. Give a linear-time algorithm (time O(jEj)) to update the tree T to the new minimum-cost spanning tree.
Given a list of n natural numbers d1, d2, ... , dn, show how to decide in polynomial time whether there exists an undirected graph G = (V; E) whose node degrees are precisely the numbers d1, d2, ... , dn. (That is, if V = v1, v2, ... , vn, then the degree of vi should be exactly di.) G should not contain multiple edges between the same pair of nodes, or "loop" edges with both endpoints equal to the same node.















As mentioned in the class, greedy algorithm is also used for neural network pruning. Please read related papers and write an essay about two pages to show your thinking. You'd better create a new LaTeX project to write this essay. Here are some papers that you can refer to and you can also nd related papers by yourself.



Yoon et al. "Combined Group and Exclusive Sparsity for Deep Neural Networks". ICML2017



Liu et al. "Learning e cient convolutional networks throughnetwork slimming". ICCV2017



He et al. "Channel Pruning for Accelerating Very Deep Neural Networks". ICCV 2017



Sun et al. "meProp: Sparsi ed Back Propagation for Accelerated Deep Learning with Reduced



Over tting". ICML2017