Prof. Avraham Melkman

Consider a fleet of vehicles comprised of K//1 identical tankers and K//2 identical nontankers (small aircraft). Tankers are capable of refueling other tankers as well as nontankers. The problem is to find that refueling sequence of the tankers that maximizes the range simultaneously attainable by all K//2 nontankers. A recent paper established that the 'unit refueling sequence', comprised of one tanker refueling at each of K//1 refueling operations, is optimal. The same paper also proffered the following conjecture for the case that the number of refueling operations is constrained to be less than the number of tankers: A nonincreasing refueling sequence is optimal. This article proves the conjecture.