Online Scheduling via Gradient Descent for Weighted Flow Time Minimization
Qingyun Chen Sungjin Im Aditya Petety





 
 

 













 


shadows
patterns





 





my crosshatch dots-1pt-1pt1pt1pt6pt6pt

    0pt0pt.5pt
    3pt3pt.5pt
    fill


properties[2][1]
	
	
	









theoremTheorem[section]
lemma[theorem]Lemma
fact[theorem]Fact
observation[theorem]Observation
proposition[theorem]Proposition
corollary[theorem]Corollary
definition[theorem]Definition
claim[theorem]Claim
assumption[theorem]Assumption
remark[theorem]Remark






#1#1






















































































true

	#1#1
	
	
	

	
	command[1]
true

	#1#1
	
	
	

	
	command[1]























Online Scheduling via Gradient Descent  for Weighted Flow Time Minimization
    
Qingyun Chen  Electrical Engineering and Computer Science, University of California, 5200 N. Lake Road, Merced CA 95344. .   Sungjin Im Electrical Engineering and Computer Science, University of California, 5200 N. Lake Road, Merced CA 95344. .  
Aditya Petety Electrical Engineering and Computer Science, University of California, 5200 N. Lake Road, Merced CA 95344. .
 

    
=========================================================================================================================================================================================================================================================================================================================================================================================

empty





§ ABSTRACT 

In this paper, we explore how a natural generalization of Shortest Remaining Processing Time (SRPT) can be a powerful meta-algorithm for online scheduling. The meta-algorithm processes jobs to maximally reduce the objective of the corresponding offline scheduling problem of the remaining jobs: minimizing the total weighted completion time of them (the residual optimum). We show that it achieves scalability for minimizing total weighted flow time when the residual optimum exhibits supermodularity. Scalability here means it is O(1)-competitive with an arbitrarily small speed augmentation advantage over the adversary, representing the best possible outcome achievable for various scheduling problems.


Thanks to this finding, our approach does not require the residual optimum to have a closed mathematical form. Consequently, we can obtain the schedule by solving a linear program, which makes our approach readily applicable to a rich body of applications. Furthermore, by establishing a novel connection to substitute valuations in Walrasian markets, we show how to achieve supermodularity, thereby obtaining scalable algorithms for various scheduling problems, such as matroid scheduling, generalized network flow, and generalized arbitrary speed-up curves, etc., and this is the first non-trivial or scalable algorithm for many of them.












§ INTRODUCTION

    


Scheduling is a fundamental algorithmic problem because it is at the heart of any resource allocation process. Because of its wide appearance in practice, scheduling has been a central field in many disciplines such as operations research and computer science. Further, scheduling problems have provided arenas where theoretical computer science has developed and tested new theory. Scheduling theory has also become richer from various points of view, such as approximation, online, stochastic, game theory, etc. In the modern era,  scheduling is giving increasing challenges and opportunities as more powerful computing resources are becoming available at low cost for novel applications.

 Online scheduling studies dynamic scheduling settings and is found in various applications.	In the online setting, the algorithm must make scheduling decisions without knowing jobs arriving in the future. Competitive analysis is commonly used to measure the quality of an online algorithm in contrast to the optimal offline algorithm <cit.>. 	Unfortunately, in competitive analysis, online algorithms are often too weak compared to their offline adversaries that know the whole input sequence from the beginning. Particularly, the effect of online scheduling algorithms making sub-optimal decisions can accrue over time, often rendering their competitive analysis pointless. 


To overcome this pessimistic landscape, in the mid-'90s, a resource augmentation model was introduced to online scheduling <cit.>.  For example, if the augmented resource is speed, which is the most commonly augmented resource, the scheduling algorithm is compared to the adversary that can process jobs slightly slower. This beyond-worst-case analysis enabled meaningful study of a large number of scheduling problems, which would otherwise not be possible <cit.>. New analysis tools have been developed for online scheduling, such as potential functions <cit.> and dual fitting <cit.>, which have resulted in a plethora of new exciting results 
for various online scheduling problems under the resource augmentation model.  

	Despite all this success, our understanding of online scheduling can be considerably improved. First of all, we only have limited ways to design online scheduling algorithms systematically. For example, the powerful online primal-dual framework <cit.> is mainly applicable for monotone packing and covering problems but a large number of scheduling problems are not as such.  Dual fitting tries to analyze a candidate algorithm by setting the primal and dual LP variables according to the algorithm's behavior. Thus, designing online scheduling algorithms still requires much creativity, often non-trivially combining commonly used scheduling strategies via repeated trial and error. There is a need to find new algorithm design strategies that can keep pace with increasingly complicated scheduling environments. 



Up to date, Proportional Fairness (PF) has been the only online meta scheduling algorithm known. The algorithm seeks to maximize the product of how fast jobs get processed at each time (subject to the scheduling constraints), and it generalizes Round-Robin.[In Round-Robin scheduling for a single machine, jobs are processed in turns after each unit of processing time. We assume that each unit of time is infinitesimally small. Under this assumption, the algorithm is equivalent to Processor Sharing, where all active jobs are processed at an equal rate at all times. In the single machine, PF solves max∏_j = 1^n z_j s.t. ∑_j z_j ≤ 1 and ≥ 0, thus yields the same assignment as Round-Robin.] It was only recently shown that PF is  O(1/ )-competitive for a large class of scheduling problems, given (e+)-speed over the adversary <cit.>. Specifically, it was shown that if we view jobs as agents and how fast they get processed as their utility, PF finds a fair resource allocation that leads to a competitive schedule for the total flow time objective. The algorithm was not new, but the main contribution was to demonstrate its effectiveness as a meta scheduling algorithm—the guarantee holds true for various problems as long as the allocation is monotone under PF.[This means that when another job is added to the PF allocation, the share or speed allocated to each existing job decreases. ] 

In this paper we aim to discover more meta scheduling algorithms that work for various scheduling environments.  
 We  focus on perhaps the most widely used metric, namely average (weighted) flow time, which measures the average time a job stays in the system from its arrival until completion. 

Roadmap. 
Due to the general applicability of our approach, we will employ somewhat heavy notation. Further, we use concepts from market equilibria, which are not commonly used in the online scheduling/algorithm literature. To make the paper more accessible, we first describe our results informally (Section <ref>) and then illustrate them using a single machine scheduling example (Section <ref>).
Readers unfamiliar with online scheduling are strongly recommended to read Section <ref> before Section <ref>. There is some intentional overlap between these sections.
    
We then formally define our problem and introduce preliminary concepts about online scheduling and substitute valuations in Section <ref>. The linear substitute results and examples discussed in Section <ref> are, to our best knowledge, new. We formally present our algorithms and theorems in Section <ref>. Section <ref> is devoted to proving the main theorems. Section <ref> demonstrates how these theorems are applied to the applications discussed in Section <ref>. Other related work is discussed in Section <ref>. Appendix <ref> discusses solving the residual optimum problem efficiently and implementing our 
 meta algorithm efficiently. All missing proofs are provided in the Appendix.







 §.§ Informal Description of Our Results and Contributions

    

We seek to find a meta scheduling algorithm that works for a large class of problems that fall into the polytope scheduling, which encompasses numerous scheduling problems <cit.>.

Polytope Scheduling.  
In the Polytope Scheduling Problem (PSP), we are given a set of constraints that form a downward-closed[If 0 ≤' ≤ and ∈, then ' ∈ P.] polytope  (more generally a convex body), which constrains the feasible processing rate vector at each time: each job j can be processed at a rate of z_j if and only if := {z_j}_j∈.

For example, we have = {  |  ∑_j z_j ≤ 1 ≥ 0} in the single machine scheduling, which says jobs can be processed at a rate of up to 1 in total.  We assume that  remains fixed over time. In the online setting, each job j arrives at time r_j with (original) processing size p_j and weight w_j.  Note that the online scheduler learns about job j, including p_j and w_j, only when it arrives. Preemption is allowed and the goal is to minimize total (weighted) flow time. 




To develop a general approach to this problem, we get an inspiration from the Shortest Remaining Processing Time (SRPT): The SRPT algorithm, which prioritizes jobs with the shortest remaining time, is well-known for optimally minimizing the average (unweighted) flow time of jobs on a single machine. Interestingly, the scheduling literature implicitly suggests a possible interpretation of SRPT as a form of gradient descent <cit.>. 
The residual optimum <cit.>, informally, is the min cost for  completing all remaining jobs, assuming no more jobs arrive. Taking gradient descent on the residual objective, meaning that we process the jobs that decrease the residual optimum the most, is natural because we complete all the remaining jobs when the residual optimum becomes zero.
Further, the spirit of gradient descent is present in the analysis based on potential functions <cit.>. 


Inspired by this, we explore gradient descent as a meta algorithm for online scheduling. Our approach is general and streamlined: i) Algorithm Execution: Solve an LP relaxation of the offline residual optimum and perform gradient descent; and ii) Performance Guarantee: If a valuation function coming from the scheduling constraints is a substitute function, gradient descent is competitive. 



Below, we outline our results and contributions.
 


    
  * First Scalable Meta-algorithm. We demonstrate the effectiveness of gradient descent as a meta-algorithm. We use gradient descent to give the first scalable algorithm for various scheduling problems, such as matroid scheduling, generalized flow scheduling, generalized arbitrary speed-up curves, etc.; see Section <ref> for the problem definition. An algorithm is called scalable if it is O(1_)-competitive with (1+) factor more speed given over the adversary.  Scalable algorithms are essentially the best one can hope for problems that have strong lower bounds on competitive ratio, and all the above problems are as such.    Since the aforementioned PF (Proportional Fairness) requires at least (2+)-speed to be O(1_)-competitive  <cit.>, our result gives the first scalable meta algorithm. We also note that we give the first non-trivial results for generalized flow scheduling and generalized arbitrary speed-up curves.  For a comparison of our results to prior work, please see Table <ref>.

     






 As discussed earlier, the concept of gradient descent is  implicitly embedded within the online scheduling literature. In this paper, we present a general approach to using gradient descent and establish a sufficient condition that ensures its competitiveness. Rather than showcasing gradient descent's applicability to several scheduling problems by case-by-case analysis, we seek a general approach that can be used to solve a wide range of scheduling problems.



      
    
  * Reduction to Obtaining an Offline (LP) Relaxation with Supermodularity. We reduce designing online scheduling algorithms to showing supermodularity of the offline residual optimum problem. The residual optimum is the minimum weighted completion time objective to complete the remaining jobs, assuming no more jobs arrive.
    
    
        
  * The (approximate) residual optimum need not have a closed-form mathematical expression. Instead, it can be computed using mathematical programming, such as time-indexed linear programming (LP). This allows us to directly derive a gradient descent-based schedule. Consequently, our approach has a wide range of potential applications. In contrast, traditional potential function analysis relies on finding closed-form expressions, which has been a major hurdle in designing and analyzing online scheduling algorithms <cit.>. Additionally, dual fitting is primarily an analysis tool, rather than a method for algorithm design.
        
        
        
        
  * We show that supermodularity of the residual optimum is a sufficient condition for gradient descent to be scalable. Intuitively, supermodularity implies adding a new job can only increase the residual optimum more when there are more existing jobs. Towards this end,  we generalize the beautiful potential function introduced by <cit.> and crystallize the analysis by identifying supermodularity as the key to the analysis.             
    


However, it is in general 
 challenging to show the residual optimum is supermodular. We address this issue by showing that it suffices to check the constraints that characterize the scheduling problem for a large class of problems. For example, 
 for scheduling m identical parallel machines (we can process up to m jobs at a rate of one at each time), we only need to 
 take a close look at the valuation function v() = max∑_0 ≤≤a· s.t. ||  ||_1 ≤ m and ||||_∞≤ 1 for some vector a≥ 0. 
 Intuitively, the valuation function means this: Given a set of jobs J', what is the maximum value we can get by choosing m jobs from J' when each job j has a value of a_j? Obviously, it is obtained by choosing m jobs with the highest value of a_j. Alternatively, one can view the valuation as the weighted rank function of a uniform matroid of rank m.
 

 
 
    
             
   
    
  * Substitutes Empower Gradient Descent. 
    We show that if maximizing a linear function subject to the constraints is a substitute function, then the residual optimum is supermodular. A valuation function is called gross/linear substitutes (GS/LS) <cit.> if increasing a resource's price does not reduce the demand for other resources. Consider the above valuation function v() for m identical machines: Items are individually priced at  and valued at a by you. If you buy m items (say 1, 2, …, m) with the maximum value of a_j - q_j (so, your utility is the valuation of the items you buy minus the payment for that), increasing item 1's price might make you buy a different item instead, but you would still want items 2,3, …, m. This shows that v() is a gross substitute; linear substitute is a continuous extension of this concept.

    Substitute valuations play a crucial role in understanding market equilibria in Walrasian markets where agents aim to maximize their utility, defined as the difference between their valuation of purchased items and the price paid. Notably, Walrasian markets admit an equilibrium when all agents have GS valuations. An equilibrium is an allocation of items to agents alongside with a price vector where every agent gets an allocation maximizing their utility and all items are allocated. Furthermore, LP duality implies that this equilibrium maximizes the total valuation of all agents, also known as social surplus.
      
   
    We view the residual optimum problem (with a sign flip) as the social surplus maximization problem in Walrasian markets. Conceptually, we introduce a phantom agent for each time slot, where each job's unit processing is a distinct item.  If the valuation function is gross/linear substitutes (GS/LS), we prove that the residual optimum is supermodular. This leverages the fact that GS/LS valuations are a subclass of submodular functions and closed under max-convolution <cit.>. This sufficient condition simplifies supermodularity checks. For example, in matroid scheduling, showing the valuation function (essentially the weighted rank) is GS/LS is easier than proving supermodularity for the entire residual optimum.

    Many scheduling scenarios involve jobs with processing rates dependent on allocated resources. To address this heterogeneity, linear substitutes (LS) <cit.> become more relevant. Linear substitutes provide a natural continuous extension of GS. Less studied than GS, LS exhibits distinct behavior. We present novel results for LS, including Theorem <ref>, which shows a concave closure of a GS valuation function is LS and Theorem <ref>, which shows generalized flow being LS. These findings hold independent interest. See Sections <ref> and <ref> for more details and formal definitions. 


Our work builds upon and extends numerous groundbreaking results that have been established throughout the history of scheduling research, e.g. <cit.>. As a consequence, we demonstrate the efficacy of gradient descent as a meta-algorithm, which has perhaps been considered a possibility by many. This work perhaps suggests that SRPT, a common topic covered in algorithms and operating systems courses, should be taught alongside its connection to gradient descent.






 §.§ Overview of Our Approach



We illustrate our approach and its benefits using the single machine scheduling problem as a running example. 

Single machine scheduling. A set of n jobs arrive over time to be processed on a single machine/processor and the scheduler is not aware of jobs that have not arrived yet. Job j has a processing time (size) p_j and arrives at time r_j. The scheduler is clairvoyant, meaning that it learns p_j upon j's arrival. The single machine can process at most one job or equivalently one unit of jobs at any point in time. Thus, letting z_j denote the rate we process job j at a time, feasible schedules are constrained by ∈ = {≥ 0   |  ∑_j z_j ≤ 1}.[If  is fractional, we can implement it by preemptive time sharing.] A job j is completed when it gets processed for p_j units of time in total. Preemption is allowed, meaning that the scheduler can preempt a job being processed and resume it from where it left off. If we denote j's completion time as C_j, its flow time[Flow time is also known as response time or waiting time.] is defined as F_j := C_j - r_j. Suppose the objective is to find an online schedule that minimizes total (or equivalently average) flow time, i.e., ∑_j F_j.

For this simple problem, as mentioned before, at each time t, SRPT (Shortest Remaining Processing Time) processes the job j with the minimum p_j(t), which denotes j's remaining size at time t, that is, p_j minus the amount of time for which it has been processed until time t. 
SRPT optimally minimizes the total flow time—intuitively, it minimizes the overall delay of job processing by processing the job it can complete the earliest. 



  §.§.§ Supermodularity Makes Gradient Descent Work (Theorem <ref>)



Let us first interpret SRPT as a form of gradient descent (GD). Suppose the current time is t. Since we would like to minimize the total flow time, ∑_j (C_j - r_j), by ignoring the cost of each job j already incurred (how long it has waited), t - r_j, pretending the current time is 0, and assuming no more jobs arrive in the future, let us try to measure the minimum cost we should pay, which is termed the residual optimum. The residual optimum then  becomes the minimum total completion time of jobs with sizes {p_j(t)}_j:


    f((t)) =   n p_π(1)(t)+ (n-1) p_π(2)(t) + (n-2) p_π(3)(t) + ⋯ + 1 p_π(n)(t),

where jobs are ordered so π(1) has the smallest remaining size and π(n) has the largest; we hide π's dependency on t for notational convenience. Note that computing f((t)) is a purely offline problem. In general, f() does not depend on a specific algorithm but only on the scheduling problem specified by the constraints, .
Given the constraint that ∑_j p_j(t) can be reduced by one at a time, GD processes job π(1), 
because it decreases f((t)) the most.  This coincides with SRPT. Thus, GD decreases the residual objective by exactly n, the number of jobs currently alive, at a time. Note that the algorithm designer  only needs to know the residual objective to derive GD. While f((t)) has a nice closed form in the single machine case, it is often NP-hard to compute exactly. In such cases, we can use linear or convex programming (Sections <ref> and <ref>).

Let ^O(t) denote the remaining job sizes under the adversary's schedule. Let A denote GD algorithm (in this case, SRPT) and O the adversary. Similarly, A(t) and O(t) imply the set of jobs currently alive at time t in their schedule; we may drop t for notational brevity.

For analysis, we use the following generic potential function Φ(t), which is directly derived from f in a black-box manner: 



    Φ(t) := 2/(f((t)) - 1/2f(  (t)  ||  ^O(t)) )
    ,


where ^O(t) := {^O_j(t) }_j denotes a vector of remaining job sizes in O's schedule and || denotes concatenation of two vectors. In other words, f(  (t) || ^O(t)) computes the residual optimum pretending that each job exists in two separate copies, with remaining sizes p_j(t) and p^O_j(t), respectively. 
As mentioned before, this abstracts away the beautiful potential function used in <cit.> for unrelated machines.[The potential function in <cit.> looks somewhat different at first sight as it measures the aggregate increase of the residual optimum when each job in A is added to O, and vice versa. But, by rearranging terms carefully, one can observe that our potential function is essentially equivalent to theirs in the setting of unrelated machines. ] 

It is known <cit.> that an online algorithm can be shown to be O(1)-competitive (with some speed augmentation) if the potential satisfies the following:


  * (P1). Φ does not increase when a job arrives or is completed by A or O.

  * (P2). / tΦ(t) ≤ - |A(t)| + O(1) |O(t)| at all the other times.

This is because Φ(t  = 0) = Φ(t = ∞) = 0 (either no jobs have arrived or all jobs have been completed) and due to (P1) and (P2), we know that 0 ≤∫_t = 0^∞/ tΦ(t)  t ≤  - ∫_t = 0^∞  |A(t)|  t+ O(1) ·∫_t = 0^∞ |O(t)|  t
(the integral is taken over the whole time except when jobs arrive or are completed.) Note that ∫_t = 0^∞  |A(t)|  t is A's objective since every job alive at time t incurs a unit cost at the time. Similarly, ∫_t = 0^∞  |O(t)|  t is O's objective. Thus we can establish A's O(1)-competitiveness. 

Unlike <cit.> that repeats trial-errors to find a potential function that satisfies these properties to analyze an online scheduling algorithm that a creative algorithm designer came up with, our approach reduces the whole algorithm design and analysis to checking if f() satisfies supermodularity. More formally, let g(Y) := f(⊙_Y)[The operation ⊙ represents component-wise multiplication.] be the residual optimum only considering jobs in Y when each job j's (remaining) size is x_j.  Supermodularity  means 
g(X ∪{j}) - g(X) ≥ g(Y ∪{j}) - g(Y)  for any j and X ⊇ Y. In other words, it implies that the increase in the residual optimum caused by the addition of a new job can only be larger if there are more jobs.

We show that we can obtain (P1) from the supermodularity of f by crystallizing the analysis of <cit.>. Further, (P2) follows from the nature of GD. In general, we can show that GD just follows the residual optimum schedule (until a new job arrives) and therefore decreases every alive job's projected completion time (counted from now) by one. Thus, the residual optimum (the minimum total completion time) decreases at a rate of s |A(t)| when  GD is given speed s > 1, i.e., / t f((t))  =  - s |A(t)|.[Speed augmentation is a common beyond-worst-case model where the algorithm with slightly higher speed is compared to the adversary with speed 1.]
By the nature of GD, this is also the maximum possible decrease rate, which is the speed times the number of jobs alive. By thinking of the processing being done on (t) || ^O(t) as a feasible schedule with speed s+1 (combining GD's speed s and the adversary's speed 1), we have 
/ t f(  (t) || ^O(t)) ≥ - (s+1) (|A(t)| + |O(t)|). Thus, (P2) follows  with s = 1+. 

In summary, we demonstrated that GD can be naturally derived from the residual optimum and its competitiveness follows from the residual optimum's supermodularity. This argument extends to an arbitrary polytope scheduling problem (Theorem <ref>). 





  §.§.§ Substitutes Empower Gradient Descent (Theorems <ref> and <ref>)

    

Theorem <ref> establishes supermodularity as a crucial structural property that ensures the effectiveness of GD. However, demonstrating supermodularity of the residual optimum is challenging for arbitrary problems, while trivial for the single-machine case. In fact, computing the residual optimum is NP-hard for many scheduling scenarios. 
Proving supermodularity without access to an efficient value oracle for the function  appears practically impossible.

To address these challenges, we can first consider an approximate residual optimum, which can be efficiently obtained by solving a time-indexed LP. Time-indexed LPs are widely used in the literature, e.g.  <cit.>. We maintain our focus on single machine scheduling for illustration.


    min∑_j, t̃≥ 1t̃/p_j z_j t̃    ∑_j z_j t̃≤ 1  ∀t̃≥ 1;   ∑_t̃≥ 1 z_j t̃≥ p_j(t)  ∀ j;   ≥ 0

Here, we use t̃ in the LP to distinguish the time variables[Here, a unit time is assumed to be sufficiently small.] from actual time t. Variable z_jt̃ implies that job j is processed at a rate of z_jt̃  at time t̃. The second constraint ensures that all jobs must be eventually completed. In general, the first constraint can be replaced with {z_j t̃}_j ∈, which encodes each scheduling problem's constraints. 
The objective is fractional since when job j is processed at time t̃ by one unit, we pretend 1/p_j fraction of it is completed by the algorithm. It is well known that an algorithm that is scalable for the fractional objective can be  converted into one that is scalable for the integer objective 
(Lemma <ref>). 
Thus, it suffices to derive GD from the fractional residual optimum. We show that we can implement GD as follows: Solve the LP and follow the solution, i.e., 
process job j at a rate of z_jt̃ at time t + t̃, until a new job arrives. We show how to make the LP compact in  Appendix <ref> to make GD run in polynomial time. 
 
However, we now face another challenge: The optimum LP solution lacks a nice structure. Despite this, how can we show the supermodularity of the optimum LP objective as a set function of jobs? To show supermodularity, we make a connection to market equilibria. To this end, by flipping the sign (and adding some large constants B), we can convert the problem into a maximization problem as follows. Now the goal becomes showing submodularity of the objective. 


    max∑_t̃≥ 1∑_j  (B - t̃/p_j) z_j t̃    ∑_j z_j t̃≤ 1  ∀t̃≥ 1;   ∑_t̃≥ 1 z_j t̃≤ p_j(t)  ∀ j;   ≥ 0


We consider the following (Walrasian) market: 
Items correspond to the remaining job sizes. Each item j exists in p_j(t) units. Each time t̃ has an agent with a valuation function,

    v_t̃() :=    ∑_j  (B - t̃/p_j) x_j,

where the function is defined over all ≥ 0 such that ||||_1 ≤ 1.[Technically we need to extend the domain of v_t̃ to encompass all non-negative vectors ≥ 0. However, we will disregard this for the sake of illustration in this section.] Suppose the items are priced at  (each unit of job j is priced at q_j). To maximize her quasi-linear utility (valuation minus payment), the agent at time t̃ buys one unit of the item/job with the maximum value of B - t̃ / p_j - q_j. 

A market equilibrium is an allocation of items to agents along with a price vector where every agent gets an assignment maximizing their utility and all items are sold out. The maximum total valuation of all agents is called the maximum social surplus, and it is well known that an equilibrium results in the maximum social surplus from LP duality.

With this interpretation, the question becomes whether the max social surplus is submodular as a set function of items/jobs. Gross substitute (GS) valuations come to the rescue here. As mentioned before, a valuation is GS if increasing one item's price does not decrease the demand for other items in the agent's optimal choice. It is trivial to see v_t̃ is GS: The agent buys the item j = max_j' B - t̃ / p_j' -q_j' and increasing any other job's price does not affect her choice; the GS condition trivially holds if we increase  j's price. 


The beauty of GS lies in the fact that if every agent has a GS valuation, then the market equilibrium exists and can be found by a tatonnement process where prices are monotonically increased from zero ensuring every item is demanded by at least one agent. In such a market, the agents with GS valuations collectively behave as a single agent with GS valuation. This aligns with the fact that GS functions are closed under max-convolution <cit.>, resulting in the max social surplus being GS.  Since GS is a subclass of submodular functions (but not vice versa) <cit.>, we can conclude that the max social surplus is submodular as a set function of items/jobs, as desired. 





 §.§ Applications

    






We outline some applications of GD.
We give scalable algorithms for all these applications—by using Theorem <ref> for the first two and by using Theorem <ref> for the third. The last application uses Theorems <ref> and <ref> with a small tweak. 
The details, including how the scheduling problems are captured by the polytope scheduling (or equivalently multidimensional scheduling) are deferred to Section <ref>.
No scalable algorithms were known for any applications below except unrelated machines, prior to our work. In particular, no positive algorithms existed for generalized flow scheduling and speed-up curves on partitioned resources.


 


  
Matroid Scheduling <cit.>. In this problem, we are given a matroid M = (J, I) where  I is a collection of job sets. The pair M = (J, I) is called a matroid if it satisfies: if I' ⊆ I and I ∈, then I' ∈; and if |I| < |I'| and I, I' ∈, then there exist j ∈ I' ∖ I such that I ∪{j'}∈. For numerous examples of matroids, see Chapter 8 of <cit.>.  At any time instant t, a feasible schedule is an independent set I in . If we schedule an independent set I of jobs, then each job in I gets processed at a rate of 1. We give a (1+)-speed O(1 / ^2)-competitive algorithm. Previously, <cit.> gave a (e+)-speed O(1 / ^2)-competitive algorithm.

Matroid scheduling encompasses many scheduling problems. As discussed earlier, a uniform matroid of rank m can model parallel identical machines (at every time step, we can process up to m jobs). A gammoid captures single-source routing in a directed graph with a single source where jobs are processed when there are vertex-disjoint paths from the source to their corresponding nodes. A cographic matroid captures edge maintenance scheduling in an undirected graph. When performing service on an edge, it becomes unusable at the moment. However, concurrent maintenance work on some edges is possible if the remaining graph stays connected without those edges. In this scenario, maintenance jobs arrive at edges. 






  
Extended Matroid Scheduling. This problem extends the matroid scheduling problem, we are given k matroids M_k = (J_k, I_k) defined the same as above. At any time instant t, a feasible schedule now is the union of the independent set I_k drawn from each matroid M_k.






  
Generalized Flow Scheduling. This generalizes the gammoid scheduling, a special case of the matroid scheduling. We are given a network G=(V,E), where J ⊆ V is the set of source nodes. Arc e has capacity u_e and flow gain factor γ_e; a flow of value f becomes γ_e f after flowing through e. Gain factors distinguish generalized flow from standard flow and are extremely useful for modeling heterogeneity, as we can have a different factor for each edge.
Job j gets processed at a rate equal to its (outgoing) net flow. It is critical for cloud computing to manage heterogeneous computing resources connected via a network; see <cit.>. A job gets processed by communicating with the resources and the heterogeneous benefit between jobs and resources can be captured by edge gain factors, e.g. <cit.>.  We give a (1+)-speed O(1 / ^2)-competitive algorithm. 
No prior work exists for generalized flow scheduling. 







  
*Speed-up Curves on Partitioned Resources. 
This generalizes the arbitrary speed-up curves model on uniform processors <cit.>, which elegantly models how the parallelization effect degrades as we use more processors to speed-up processing a job. 
There are D different divisible resources, where the ith resource exists in m_i units. 

At every time, resources are allocated to jobs.
Each job has a valuation function of the following form: Resources are partitioned into k disjoint groups G = G_1, ..., G_k; partitioning can be different for each job. Each group G_i ∈G is associated with a monotone univariate concave function g_i: _+ →_+ with g_i(0) = 0. Then, the processing rate of job j is v_j(_j) = ∑_i=1^k g_i(∑_d ∈ G_i a_jd x_jd),  where a_jd≥ 0, when j receives  _j = (x_j1, x_j2, ..., x_jD) resources. Concave functions are used to model the diminishing returns of parallelization as we add more computing resources. The former arbitrary speed-up curves is a special case of this model when D = 1.  
We give a (1+)-speed O(1 / ^2)-competitive algorithm. No prior work exists for this problem. 



To see why this general model is useful, suppose D = 2 and consider three types of valuation functions:  x_j1^.5, x_j2^.75, and (x_j1+ x_j2)^.5, for an example. The first means the job can only use processors in G_1, and the second means the job can only use those in  G_2, but the third can use any processors. This can model the restriction of processors available for each job's processing. CPU partitioning is common in practice <cit.>. 



 





  
Unrelated Machines <cit.>.  There is a set of parallel machines. Each job j gets processed at a rate of  λ_ij when scheduled on machine i; this is equivalent to j having a processing time p_j / λ_ij if scheduled only on machine i. Each job can be processed by at most one machine at any point in time. 

We first reproduce the seminal result in <cit.>, which gave a (1+)-speed O(1/ )-competitive algorithm for minimizing total weighted flow time (Section <ref>). We use the same algorithm of <cit.>,  which immediately dispatches an arriving job to one of the machines and keeps the job on the same machine until its completion. Perhaps, the analysis of <cit.> becomes more transparent through the lens of our framework, supermodularity and gradient descent. 

While <cit.> gave essentially the best possible result and we can recover it, the work left an intriguing question from a technical point of view. Although immediate-dispatch and non-migration are highly desirable, they were strongly required in the analysis; it was not known whether we could still achieve a competitive algorithm if we migrated jobs in the middle of the execution for better load balancing. This has been puzzling in the research of online scheduling algorithms. 


Our approach answers this question positively by providing a scalable algorithm that changes job assignments when a new job arrives to achieve better load balancing. Furthermore, our algorithm is purely Markovian, meaning it only needs to remember the amount of jobs processed, eliminating the need to track job assignments. Specifically, we present a (1+)-speed, O(1 / )-competitive algorithm for unweighted total flow time (Section <ref>) and a (1+)-speed, O(1 / ^3)-competitive algorithm for weighted total flow time (Section <ref>). While this result has a worse competitive ratio for the weighted case and is migratory, we believe the Markovian property has the potential for broader applications; see Section <ref>.






 





 §.§ Comparison with the Previous Work



As mentioned, Proportional Fairness (PF) <cit.> is the only online scheduling meta-algorithm known other than our gradient descent (GD). PF finds a fair allocation in Fisher markets, where each agent (job j) starts with an endowment (job j's weight w_j) and buys some resources to maximize its valuation (how fast it gets processed at the moment). PF solves max∑_j w_j log v_j(_j) s.t. ∑_j_j ≤, ≥ 0 where j has valuation v(_j) when it receives _j resources from the supply vector of divisible resources.[Equivalently, the scheduling problem can be expressed as a polytope  that describes how fast jobs can be processed, i.e., := { x_j = v_j(_j)   |  ∑_j _j ≤ 1, ≥ 0}.]  The solution can be viewed as an equilibrium where the market is cleared under the corresponding dual prices of the resources. Note that PF 
finds an instantaneous fair allocation without factoring in job sizes, hence is non-clairvoyant. The main contribution of <cit.> lies in showing that PF is O(1_)-competitive with (e+ )-speed for the total weighted flow time objective for  scheduling problems when the allocation under PF is monotone—a job's speed/share can only decrease when other jobs arrive. 




Although PF is a remarkable meta-algorithm generalizing RR (Round-Robin), it exhibits limitations from an algorithm design point of view. It is because we lose all the nice properties of PF when we deviate from the equilibrium it finds. Thus, it is not clear how to reduce the speed requirement of the algorithm; even RR requires (2+)-speed over the adversary for competitiveness. 
Moreover, it disregards job sizes in scheduling decisions, a crucial aspect for designing machine learning-augmented algorithms that leverage job size estimates, a topic of recent significant interest <cit.>. 

Driven by these considerations, we investigate GD as a meta-algorithm, as the spirit of GD is often ingrained in online scheduling. Furthermore, unlike PF, GD offers flexibility. Implementing GD requires an estimate of the remaining cost. One common method of obtaining this estimate is to first fix a candidate algorithm and derive a reasonably accurate estimate of its remaining cost, which is converted into a potential function of a nice mathematical form <cit.>. However, this approach demands algorithmic creativity, which involves a lot of trial and error. 

Alternatively, one can utilize the (approximately) optimal remaining cost, also known as the residual optimum. Note that the residual optimum is not tied to specific algorithms. However, computing the residual optimum is often NP-hard, rendering it challenging to understand its evolution. One approach is employing an LP relaxation, but this results in an LP solution, which commonly lacks structure. 


Our work draws upon critical ideas from the seminal work of  <cit.>, which presented the first scalable algorithm for unrelated machines; see <ref> for more details.  They introduced an elegant potential function, and our meta-potential function is its generalization. 

Generalizing their work poses challenges. Their algorithm executes SRPT (or its weighted version) on each machine following the initial assignment, and SRPT admits a closed-form expression for the residual optimum. Their potential function computes the residual optimum for a mixture of jobs from the algorithm and the adversary. However, determining how to proceed when the residual optimum lacks a convenient closed-form mathematical expression remains unclear. 

We address the challenges as follows. First, we abstract away the potential function argument presented in <cit.> and demonstrate that their potential function can be generalized to work solely with supermodularity when gradient descent is employed. Furthermore, by establishing a novel connection to Walrasian markets, we simplify the task of verifying whether the residual optimum is supermodular.

 
The connection we make between gradient descent to Walrasian markets is less obvious than PF's connection to the Fisher markets. It is well-known that PF finds a market-clearing equilibrium in the Fisher market, but it is unclear how markets are related to the residual optimum. In Walrasian markets, agents have no endowments and they try to maximize their quasi-linear utility, which is their valuation minus the payment for the resources bought. We use gross substitutes[It is important to note that they have different definitions in Fisher and Walrasian markets.] and linear substitutes to find sufficient conditions to obtain supermodularity. 





Finally, PF and GD are somewhat complementary to each other. 
PF makes scheduling decisions without knowing job sizes but uses (e+) speed to be O(1)-competitive. On the other hand, GD only needs (1+) speed augmentation. Further, there are problems for which one is O(1)-competitive (with O(1)-speed augmentation), but not the other. For example, for broadcast scheduling PF is O(1)-competitive, but not gradient descent (Appendix <ref>). For unrelated machines, PF is believed not to be O(1)-competitive <cit.>, but we show gradient descent is (Sections <ref>, <ref>, and <ref>).













 §.§ Future Work

    

In this paper, we show a reduction from designing online scheduling problems to the offline problem of finding an LP relaxation whose optimum satisfies supermodularity. In particular, we show if the underlying valuation function subject to the polytope characterizing the scheduling constraints at each time satisfies substitute properties, gradient descent is scalable. We discuss several open problems below. 


    
  * Gradient descent does not yield an O(1)-competitive algorithm for all scheduling problems as mentioned above (Appendix <ref>).       
    Can we find other sufficient conditions for GD to be O(1)-competitive? For example, can we design algorithms for the intersection of two matroids?     
    The matroid intersection is known not to be  a gross substitute <cit.>. Here, it may increase the required speed or  competitive ratio. 
    
    
  * Can we extend gradient descent to ℓ_k-norms of flow time? Although a naive extension of our framework to ℓ_k-norms seems to create an undesirable increase of the potential due to job ages, we believe it should not be a major roadblock.  No meta-algorithms have been  considered for  ℓ_k-norms of flow. We have some preliminary results for this objective. 
    
    
  * Is there an online algorithm for minimizing ℓ_k-norms of flow time where the competitive ratio has no dependency on k? For unrelated machines, there exist (1+)-speed O(k)-competitive immediate-dispatch algorithms <cit.>. However, it is known that any immediate dispatch algorithm must have a linear dependency on k <cit.>.  Since there exists a scalable algorithm for the maximum unweighted flow time with no dependency on k, it is plausible to remove the dependency by considering migratory algorithms <cit.>. As discussed, our algorithm allows migration, and thus has the potential to solve this problem.

    
  * Can we develop another nonclairvoyant meta-algorithm besides PF? PF generalizes Round Robin, which requires at least (2+)-speed to be O(1)-competitive. However, Shortest Elapsed Time First (SETF)[In the single machine scheduling, SETF processes the job that has been processed the least.] is known to be scalable in the single-machine setting and uses information about how much jobs have been processed. Can we generalize SETF in a similar way that SRPT and Round Robin were generalized to gradient descent and PF?
    
    
    






 













§ PRELIMINARIES

    



 §.§ Common Notation
 We use _X to denote a binary vector corresponding to X. We use bold fonts for vectors. For two vectors ,, ∧ takes the component-wise min of  and . Similarly, ∨ takes the component-wise max of  and . We let 
⊙ denote the component-wise multiplication  of  and . When v is a set function, we will interchangeably use v(X) and v(_X) for a set X.




 §.§ Problem Definition and Scheduling Primitives

    

For easy reference, we reproduce the definition of the polytope scheduling below. All scheduling problems we will study fall into the polytope scheduling problem, or equivalently multidimensional scheduling. 



  
Polytope Scheduling (Feasible Processing Rate View). Most preemptive scheduling problems with fixed computing resources can be represented as an instance of the polytope scheduling problem (PSP) <cit.>. In the PSP, we are given a set of constraints that form a downward-closed[If ' ≤ and ∈, then ' ∈.] polytope  (more generally a convex body), which encodes the feasible processing rate vector at each time: each job j can be processed at a rate of z_j if and only if := {z_j}_j∈.

For example, we have = {  |  ∑_j z_j ≤ 1 ≥ 0} in the single machine scheduling, which says jobs can be processed at a rate of up to 1 in total. 
We assume that  remains fixed over time. 





  
Multi-dimensional Scheduling (Resource View). Equivalently, the PSP can be viewed as multidimensional scheduling where each dimension corresponds to a distinct resource. There exists a set of D divisible resources or a continuous supply vector ,[We can assume wlog that every resource exists by one unit by scaling.] which are replenished at each time. Each job j is associated with a concave valuation function, u_j: [0, 1]^D→_+, which denotes how fast it gets processed. A feasible allocation is constrained by ∑_j _j ≤: Job j gets assigned a resource vector _j and gets processed at a rate of u_j(_j). We will call this resource view and the above feasible processing rate view. 







We consider the clairvoyant scheduling setting: Each job j arrives at time r_j with (original) processing size p_j and weight w_j. Note that the online scheduler learns about job j, including w_j and p_j, only when it arrives. A job is completed when it has been processed by p_j units since its arrival time r_j. Preemption is allowed, meaning a job can be paused and resumed later. Our goal is to minimize the following objective function.





  
Total Weighted Flow Time. For integral flow time objective, an individual job j's flow-time is defined as F_j = C_j - r_j which is the difference between its arrival time r_j and  completion time C_j; we may add σ to C_j as superscript to make clear the schedule σ considered. Note that C_j is defined the min time t' such that ∫_t = r_j^t' z_j(t)  t = p_j, where z_j(t) is the processing rate of job j at time t in the schedule σ. 
Then, the total weighted integral flow time is ∑_j ∈ J w_j F_j, where w_j is the weight of job j and J is the entire set of jobs arriving to be completed. 



  
Speed Augmentation. A large number of scheduling problems do not admit O(1)-competitive algorithms. In such cases, speed augmentation is commonly used for beyond-worst-case analysis. Here, the online scheduling algorithm runs with extra speed compared to the optimal scheduler. If an algorithm can process s >1 times more than the adversary can process at a time and has an objective at most c times than the adversary does, we say that the algorithm is s-speed c-competitive. 
Intuitively, this implies that the algorithm can handle 1 / s-fraction of what the optimum solution can handle <cit.>. Thus, an algorithm that is O(1_)-competitive with (1 + )-speed for any > 0 is of fundamental importance and termed  scalable.




  
Total Fractional Weighted Flow Time. In many scenarios, we will consider the fractional flow time which is a relaxation of integral flow time. The fractional weighted flow time objective is defined to be ∑_j ∈ J∫_t ≥ 0w_j/p_j t z_j(t)  t. In other words, we view {z_j(t) / p_j}_t as a distribution when the job is completed. By definition, it is obvious that a job's fractional flow time is no greater than its integer flow time in any fixed schedule. It is easier to minimize fractional flow time than integer flow time. Fortunately, with an extra speed augmentation, we can convert an algorithm that is good for fractional flow time into one that is good for integer flow time. 








    
    For any polytope scheduling problem, we can convert an online algorithm whose total fractional weighted flow time is C into an online algorithm with (integer) weighted flow time O(C / ) given (1+)-speed. Therefore, if there is an online scheduling algorithm that is c-competitive with s > 1 speed for total fractional weighted flow time, then for any > 0, there exists an algorithm that is s(1+)-speed O(c / )-competitive for total (integral) weighted flow time. 



For a fixed schedule σ, we will let σ(t) := {j   |   r_j ≤ t < C^σ_j}  denote the set of jobs alive at time t in σ. We will often use A and O to denote our algorithm('s schedule) and the adversary('s schedule), respectively. As an alive job j adds w_j at each time to the total weighted flow time objective, we immediately have the following. 


    
    We have ∫_t = 0^∞  W^σ(t)  t = ∑_j w_j (C^σ_j - r_j), where W^σ(t) := ∑_j ∈σ(t) w_j is the total weight of jobs alive at time t in σ. 



This observation also extends to the fractional objective. Let p^σ_j(t) be j's remaining size at time t in schedule σ.


    
    We have ∫_t = 0^∞W̃^σ(t)  t = ∑_j w_j ∫_t = r_j^∞z_j^σ(t)/p_j t  t, the total fractional weighted flow time of σ, where W̃^σ(t) := ∑_j ∈σ(t) w_j p_j^σ(t)/p_j is the total fractional weight of jobs alive at time t in σ. 











 §.§ Gross Substitutes for Indivisible Resources

    

  



We first consider valuation functions for indivisible items.  Note that we consider the Walrasian market model throughout this paper, which is different from the Fisher market, as discussed in Section <ref>. Formally, the Walrasian market is defined as follows.



    A Walrasian market consists of a set of n indivisible items and m agents where  each agent i ∈ [m] has a valuation function v_i: 2^[n]→. Each item j ∈ [n] is priced at q_j ∈_+. Then, the market gives a disjoint allocation { S_i}_i∈[m] of items over agents. We define the social surplus of the market as ∑_i ∈[m] v_i(S_i). 


In the Walrasian market, each agent has a preference for bundles of items specified by the quasi-linear utility function, which can be formally defined by the demand correspondence as follows.



    Given a set function v : 2^[n]→ and a price vector ∈_+^n, we define the demand correspondence (or set) D(v, ) as the family of sets that maximize the quasi-linear utility of the agent:
    
    D(v, ) := max_Xv(X) - ·_X.



In other words, D(v, ) represents the set of item subsets that maximize our total happiness (the difference between our valuation and the total cost) under the price vector , given our valuation function v. The Walrasian equilibrium asks that every agent maximizes its utility function and all items are allocated. Formally, the Walrasian equilibrium is defined as follows.




    Given a Walrasian market with n indivisible items and m agents with valuations {v_i}_i ∈ [m], a Walrasian equilibrium consists of a partition { S_i}_i∈[m] of n and a price vector ∈^n_+ such that   
    S_i ∈D(v_i,) for all i ∈ [m]. 





It is known that an equilibrium exists if all agents' valuation function satisfies the GS property. GS is an important class of valuation functions <cit.>. 




    A valuation function v : 2^[n]→ is gross-substitute (GS) if for any price vectors ' ≥≥ 0 and any X ∈D(v, ), there is a set Y ∈D(v, ') such that X ∩j : q_j = q'_j⊆ Y.



In other words, a GS valuation means that if we increase an item j's price, we can update an optimum allocation without dropping any other items. Intuitively, this is possible because j can be substituted with other items unlike some items behaving like a bundle, e.g. milk and cereal.

It is known that GS is a strict subclass of submodular functions <cit.>.



    
    A valuation function v: 2^[n]→ is submodular if for all X, Y ⊆ [n], v(X) + v(Y) ≥ v(X ∩ Y) + v(X ∪ Y). Alternatively, it is submodular if v(X ∪{e}) - v(X) ≤ v(Y ∪{e}) - v(Y) for all X ⊇ Y and e ∈ [n].     
    Symmetrically, v is supermodular if -v is submodular. 



    
    A valuation function v that satisfies the GS property is submodular.


Furthermore, Lehmann, Lehmann and Nisan <cit.> showed GS 
valuations are closed under convolution, meaning that the aggregate max-valuation of GS valuations is GS. 



    
    The class of gross-substitute valuations is closed under convolution, i.e., for any two gross-substitute valuations v_1 and v_2, v_1 ⊕ v_2 is gross substitutes, where 
    
    v_1 ⊕ v_2 (S) = max_T ⊆ Sv_1(T) + v_2(S ∖ T)



It is known that a Walrasian equilibrium exists when all agents have GS valuations, and a Walrasian equilbrium results in the max social surplus <cit.>. Thus, the lemma can also be interpreted as stating that the social surplus of a Walrasian market exhibits GS if all agents have GS valuations.








  §.§.§ Examples

    

We state a few examples of GS valuation functions. For a comprehensive list, see <cit.>. 

    
  * Symmetric concave functions: f: 0, 1^n→∪{∞} is a symmetric concave function if there exists a concave function φ: _+ → s.t f() = φ(∑_i=1^nx_i ). 
    
    
  * Laminar concave functions: A set family 𝒯⊆ 2^N is laminar if X ∩ Y = ∅, X ⊆ Y or X ⊇ Y for every X ≠ Y ⊆𝒯. Define φ_Y: _+→ to be a univariate concave function. Then the function given by f(x) = ∑_Y ∈𝒯φ_Y(∑_i ∈ Y x_i ) is called a laminar concave function.
    
    
  * Maximum weight bipartite matching: Let G=(U, W; E) be a weighted bipartite graph with an edge cost function w : E →. Define  f : 0, 1^n →∪-∞ to be the maximum weight bipartite matching w.r.t a vertex set X ⊆ U by
    
    f(_X) = max{∑_e ∈ M w(e)  |  M ⊆ E is a matching in G covers all vertices in X}
 
       
    
    
  * Weighted rank functions of matroids: Let M = (E, ℐ) be a matroid (see Section <ref> for definition), where E is a universe of n elements, and I ⊆ 2^E is a collection of independent sets. Let w : E →_+ be a weight function. Then define f: 0, 1^n →_+ to be the weighted rank function w.r.t an element set X ⊆ E, i.e., 
    f(_X) = max{∑_i ∈ Yw(i)  |  Y ⊆ X, Y ∈ℐ}
 
        
    




 §.§ Linear Substitutes for Divisible Resources



Since we consider preemptive schedules where jobs can be processed by fractional amounts at a time and we will handle heterogeneous resources, we need a continuous extension of GS and Walrasian markets where resources to be allocated are divisible. 
Continuous definitions of gross substitutes, termed linear substitutes (LS),  were introduced by Milgrom and Strulovici <cit.>.
 Interestingly, although the continuous setting does not inherit all properties that are guaranteed in the discrete setting <cit.>, LS still offers some useful properties we can leverage. In particular, LS valuations also are closed under convolution (or equivalently called aggregation) and are a subclass of submodular functions.[For a continuous function v, submodularity is defined analogously to Definition <ref>: 
  v() + v() ≥ v(∨) + v(∧). 
 
  Further, v is supermodular iff -v is submodular.] 




    v: ∏_i ∈ [n] [0, L_i] → is a linear-substitute valuation if for any price vector  and ', then whenever q_j ≤ q'_j, q_k = q'_k for all k ≠ j and X ∈D(v, ), there is a Y ∈D(v, ') such that Y_k ≥ X_k for all k ≠ j. 




    
    The class of linear-substitute valuations is closed under aggregation, i.e., for any linear-substitute valuations v_1, ..., v_n, v is linear substitutes, where 
    
    v() = max∑_i ∈ [n]v_i(_i) : ∑_i ∈ [n]_i = , _i ≥ 0  ∀ i ∈ [n]



Similar to GS, this lemma implies that the social surplus is LS if all the agents have LS valuations in the Walrasian market considered. 

To verify the LS property, we can check the submodularity of its dual profit function.


    
    v : ^n→ is a linear-substitute valuation iff π is submodular, where 
    
    π() := max_∈^n v() - ·



We can easily extend the proof of GS implying submodularity (Lemma 5 in <cit.>)  to LS implying submodularity; for completeness, we give the proof in Appendix <ref>.




    
    Let v : ^n → be a concave linear-substitute valuation. Then, v() is submodular.




  §.§.§ Examples
 

We discuss some examples of linear substitutes, which will be used as building blocks in applying our theorems. Compared to gross substitutes, relatively fewer examples are known in the literature. We show that the concave closure of GS and generalized flow satisfy LS, which could be of independent interest; the proofs are deferred to Appendix <ref>. 
For more examples, see Section 5 of <cit.>.






[Concave Closure of Gross Substitutes is LS]theoremThmGsClosure
    
    Given a gross-substitute valuation v : 0, 1^n →, let v^+() := max∑_S v(S) λ_S : ∑_Sλ_S _S = , ∑_Sλ_S = 1, λ_S ≥ 0 be the concave closure of v. Then, v^+(): [0, 1]^n  →_+ is linear substitute.    


To keep the flow of presentation, we defer the formal definition of generalized flow to Section <ref>. 





    
    For any cost vector , v() := max_∈· for the  in Eqn. (<ref>), which is defined for generalized flow, 
    
   is LS.







§ FORMAL DESCRIPTION OF OUR RESULTS

    







 §.§ Gradient Descent on the Residual Objective




We begin by formally defining the residual objective at each time t, namely the minimum projected cost of the remaining schedule. Let A(t) := { j   |   r_j ≤ t < C_j} be the set of jobs alive at time t in our schedule. Let p_j(t) denote j's remaining size at time t; by definition, p_j(t) = 0 for all t ≥ C_j. Since the objective we consider is a linear combination of jobs' flow time, we can observe that w_j (C_j - t), is exactly how much j will contribute to the objective from time t until it is completed at time C_j as  j gets processed by p_j(t) units  by the algorithm  during [t, C_j]. So, if we shift time by t for easy indexing, we have the following residual scheduling problem: Each alive job that has arrived has a (remaining) size p_j(t) and has arrival time 0 (in the shifted time horizon), and weight w_j. Noticing that completion time is equivalent to flow time when jobs arrive at time 0, the residual optimum can be expressed as follows.
 

    f() :=   min∑_j ∈ A(t)    w_j C̃_j     s.t.  
    ∫_t̃≥ 0^C̃_j z_j(t̃) t̃   = x_j   ∀ j ∈ A(t) 
    (t̃)    ∈  ∀t̃≥ 0,

where we set x_j = p_j(t) for all j ∈ A(t).  Note that we added tilde to C_j and t to make it clear that we are considering the shifted time horizon. The first constraint ensures that every job j must be processed by x_j units, and the second guarantees feasible scheduling at every time.


Let ^_() denote the objective of ^_ for . In other words, ^_() is the extra cost we should pay if we follow  from time t, i.e., process each job j at a rate of _j(t̃) at time t + t̃, assuming no more jobs arrive.  If  is infeasible, then let ^_() = ∞. Let f() := min_^_(), which we will term algorithm A's (integral) residual optimum at time t. 

We are now ready to formally define our gradient descent algorithm: At each
time t we try to decrease f() the most, i.e.,


    min_∇ f()  |_ = (t)   ·
       ∈


We will let ^() denote the decrease of the integral residual optimum due to the gradient descent, i.e., the optimum to Eqn. (<ref>).   However, we will see that if (t̃) for t̃≥ 0 is an optimum solution that achieves f((t)), to implement GD, we can simply process jobs according to (0) at time t. In fact, we will show that we can exactly follow the residual optimum schedule until a new job arrives (Lemma <ref>).  For brevity, we may omit  from notation. 


Notably, we take this time-indexed view since it explicitly describes the residual optimum solution at each time. Let us illustrate this with a single machine scheduling example we discussed in Section <ref>: After solving ^_(t) we obtain: z_π(j)(t̃) = 1 for t̃∈ [0, p_π(1)(t)) only for j = 1 (0 for all other jobs), z_π(j)(t̃) = 1 for t̃∈ [p_π(1)(t), p_π(1)(t)+ p_π(2)(t)) only for j = 2, and so forth. By solving Eqn.(<ref>), we obtain  such that z_π(1) = 1 and z_π(j) = 0 for all j ≠ 1. Note 
that  is identical to (0). This is not a coincidence. Lemma <ref> says that we can follow (t̃) to implement GD: process job π(1) during time 
[t, t+ p_π(1)(t)) and job π(2) during [t+p_π(1)(t), t+ p_π(1)(t)+ p_π(2)(t)), and so forth. This is exactly what SRPT does. 

In the following, we define the key desired property we use in our paper: for any fixed remaining job sizes , the residual optimum viewed as a set function is supermodular. There is an extended notion of submodularity/supermodularity in the continuous setting which is needed for linear substitutes (Section <ref>). However, this notion of supermodularity is sufficient for our purpose here. For brevity, we may simply say supermodularity without explicitly mentioning `discrete.'


    
    We say a function g: ^|J|_≥ 0→ is 

        (discrete-)supermodular if for any fixed ,  g̅_(Z) := g(⊙_Z): 2^J→ is supermodular, i.e., g̅(U) + g̅(V) ≤g̅(U ∩ V) + g̅(U ∪ V) for all U, V ⊆ J, where 
        _Z is the binary characteristic vector of Z for any Z ⊆ J and 
        ⊙ denotes component-wise multiplication.


We identify supermodularity as a key sufficient condition for the gradient descent on the optimum integral residual objective to give a scalable online algorithm by the following theorem. 

[Gradient Descent Desiderata for Integral Objective]theoremthmone

 For a polytope scheduling problem with polytope ,  
 suppose f() := min_^_() is discrete-supermodular.
     Then, for any > 0, GD is (1+)-speed O(1 / )-competitive for minimizing weighted integral flow time for PSP . 







 §.§ Substitutes Empower Gradient Descent

    

 
Unfortunately, a large number of scheduling problems are NP-hard to optimize for the integral completion objective.

Further, it is non-trivial to check if the residual optimum objective is supermodular. Thus, to make the gradient descent framework more readily applicable, we consider a fractional version of the residual objective and show it satisfies supermodularity for a large class of scheduling problems related to substitute valuation functions. Recall that we can use a standard conversion to translate an algorithm that is scalable for fractional weighted flow into one that is scalable for integer weighted flow; see Lemma <ref>. 

As discussed in Section <ref>, we can take the feasible processing rate view (polytope scheduling) or equivalently the resource view (multi-dimensional scheduling). In the following, we consider both views.




  §.§.§ Feasible Processing Rate View


The following is a well-known time-indexed LP <cit.>, which we will use to measure our fractional residual objective. As before, we use t̃ to distinguish the time used in the residual schedule from the global time t.



    f():= min∑_j ∈ A(t)   w_j/p_j∫_t̃≥ 0t̃· z_j(t̃) t̃   
    ∫_t̃≥ 0 z_j(t̃) t̃   = x_j   ∀ j ∈ A(t) 
    (t̃)    ∈  ∀t̃≥ 0


This LP tries to minimize total weighted fractional completion time. 
Gradient descent on f() := min_^_() solves min∇ f()  |_ = (t)· subject to ∈ and processes jobs at time t + t̃ according to (t̃), but as before, we will show that we can follow the LP solution until a new job arrives. 

[Gradient Descent Works for Linear Substitutes in Feasible Processing Rate View]theoremthmtwo
    
    For a polytope scheduling problem with polytope , suppose that for any ∈_+^|J|, v() = max_0 ≤≤, ∈· is linear substitute. Then, for any > 0, the GD gives a (1 + )-speed O(1 / )-competitive online algorithm for minimizing total fractional weighted flow time; thus, there exists a (1+)-speed O(1 / ^2)-competitive algorithm for total weighted flow time.  


The theorem can be proved separately for gross substitutes (GS) for indivisible resources. However, we only state the theorem for linear substitutes (LS) because we can show that the concave closure of GS is LS (Theorem <ref>). The conceptual contribution of the theorem lies in connecting GD to substitute valuation.



The time-indexed LP could be exponentially large. 
In Appendix <ref>, we show that we can consider an approximate residual optimum to obtain a polynomial time 
algorithm—assuming that we have an efficient oracle to test whether ' ∈ or not. 





  §.§.§ Resource View
 

We now consider the other equivalent view where each job gets some resources at each time from a D-dimensional supply resource vector , which is replenished at every time. Recall that each job j is associated with a valuation function u_j. Let _jt denote the resource vector job j receives at time t. Job j then gets processed at a rate of u_j(_jt). We will keep reserving t̃ to refer to times in the residual schedule. The LP we solve is essentially identical to ^_, but has more explicit constraints that resources cannot be over-allocated. Concretely, we use the following linear programming.



    f() := min∑_j   w_j/p_j∫_t̃≥ 0t̃· u_j(_jt̃) t̃   
    ∫_t̃≥ 0 u_j(_jt̃) t̃   = x_j   ∀ j 
    ∑_j_j t̃   ≤  ∀t̃≥ 0


We prove the following theorem. 


[Gradient Descent Works for Linear Substitutes in Resource View]theoremthmthree
    
    For a multi-dimensional scheduling problem with a supply vector  of divisible resources, suppose that for every job j, u_j : [0, 1]^D→_+ is strictly monotone and strictly concave[Under this assumption, the demand set is a singleton set.] linear substitute  and further satisfies the following:
    
        
  * For any ∈D(u_j, ) and λ≥ 1, there exists ' ∈D(u_j, λ) such that ≥'.
        
  * For any ∈D(u_j, ) and ' ≤, there exists ' ∈D(u_j, ') such that u_j(') ≥ u_j().          
        
    Then, for any > 0, the GD applied to _(t)
    yields a (1 + )-speed O(1 / )-competitive online algorithm for minimizing total fractional weighted flow time; thus, there exists a (1+)-speed O(1 / ^2)-competitive algorithm for integer weigthed flow time. 


In the theorem, in addition to every job j having an LS valuation function, we require two additional properties. The first says that if we increase all prices by the same factor, then each job demands only less resources. The second says that if we increase resource prices, each job's optimal demand maximizing its quasi-linear utility should have a lower valuation. While these two properties are intuitive, not all LS valuations satisfy them[For example,  u() := max∑_i λ_i y'_i  s.t. ||'||_1 ≤ 1 and ||'||_1 ≤ ||||_1 is LS, but does not satisfy the first property.].


To prove the theorem, we show that the valuation functions considered here induce an LS function in the feasible processing rate view, which allows us to use Theorem <ref>. The high-level proof idea is as follows. Consider v() = max_0 ≤≤, ∈· for a fixed . 
We want to show the valuation v is LS. Let  be the job prices per unit. 
By processing job j by one unit, we obtain value c_j, yet have to pay the price q_j. Finding the demand set for v  can be viewed as finding the maximum social surplus when each job (agent) j has valuation (c_j - q_j)u_j in the resource view; let  be the equilibrium prices of the D resources. 
Increasing q_j lowers (c_j - q_j)u_j, which has the same effect of increasing the resource prices  for j by a certain factor λ > 1.  Thus it results in resources being under-utilized due to the first property. Then, it is known that the  equilibrium prices drop <cit.>. All jobs' valuation functions (c_i - q_i) u_i, except for j, remain the same. Therefore, they can only get processed more due to the second property. 








§ PROOFS OF MAIN THEOREMS

    





 §.§ Proof of Theorem <ref>

    


It is highly important to note that in the proof when a job j arrives, we pretend that GD and the optimum schedule each are given a distinct copy of j. Therefore, if A(t) and O(t) denote the sets of jobs that have arrived yet have not been completed at time t by GD and by the optimum schedule respectively, then A(t) ∩ O(t) = ∅ always. We will use A and O to denote GD's schedule and the optimum schedule, respectively.  

We use || to denote the concatenation of two vectors  and . Let p^A_j(t) and p^O_j(t) denote the remaining size of job j under our algorithm GD and a fixed optimum schedule respectively. For brevity we let ^A(t) := {p^A_j(t)}_j ∈ A(t) and ^O(t) := {p^O_j(t)}_j ∈ O(t). For analysis, we will use the following potential function. 


    Φ(t) = 2/(f(^A(t)) - 1/2f(^A(t) || ^O(t)))




Following the standard potential function argument in online scheduling <cit.> we will show the following:


    
  * Boundary Conditions: Φ(0) = Φ(∞) = 0. In other words, at the beginning when no jobs have arrived, and at the end when all jobs have been completed, the potential is 0. This is obvious because the residual optimum is 0 when there are no jobs to be processed and it is only concerned with processing jobs that are currently alive. Further, it's worth noting that jobs of zero remaining sizes have no effect on the residual optimum.
    
    
  * Discrete Changes: Φ does not increase when a job arrives or is completed by GD or the optimum schedule. To this end, we will crucially use supermodularity.
    
  * Continuous Changes: Φ(t)/ t≤ - W^A(t) + O(1/) W^O(t), when A is given 1+ speed and O 1-speed, where W^A(t) : = ∑_j ∈ A(t) w_j and W^O(t) := ∑_j ∈ O(t) w_j denote the total weight of jobs alive at time t in GD's schedule and the optimum's, respectively. 





Recall that ^() := - min_∈∇ f() · denotes the change rate of the residual optimum for remaining sizes  due to GD's processing. 
As mentioned earlier, the  can be dropped for convenience, so () denotes the same concept. If GD uses speed s, we denote it as _s().
Note that GD with s speed can process jobs at rates s if ∈. 


    
    For any s >0, we have _s() = -  s().




The following lemma proves that the change in the optimal residual objective value due to GD is precisely equal to the total weight of the uncompleted jobs. The intuition is simple: the residual optimal schedule remains optimal for minimizing total weighted completion time until a new job arrives. Consequently, every job's completion time in the residual schedule decreases by one in each time step. This establishes the “≤" direction. The other direction can be proven similarly.



    
    When the residual optimum is f() := min_^_(), we have () = - ∑_x_j>0w_j.



    Let (τ), τ∈ [0, +∞) be the optimal residual schedule for remaining size , i.e., = min_'^_('). Consider the decrease of the residual optimum in t units of time when we run GD. Let t be an infinitesimally small time step such that no job is completed during time [0,  t). Recall that GD schedules (τ), τ∈ [0,  t). Let (τ') := ∫_τ”≥ 0^τ'(τ”) τ”. Let ' =  - ( t) be the remaining sizes after processing  in t time. Note that '(τ) := (τ +  t), τ∈ [0, ∞) is a feasible schedule, for remaining job sizes '. Then we have f(') ≤_'^(') because f(') minimizes ^_' w.r.t.  remaining sizes ', and ' is a feasible schedule w.r.t. the same vector '. Thus we have
     
    
    f() - f(') ≥^_()- ^_'(') =  t ∑_x_j>0w_j

    
    This is because every job j s.t. x_j > 0 has a t units larger completion time in  than in schedule ' and is still alive in the infinitesimally time step. Formally, j completes in  at the maximum (supremum) time c such that z_cj > 0, and therefore it completes at time c -  t in ' since (c) = '(c -  t). 
    


To show the other direction, suppose GD schedules ”(τ) for τ∈ [0,  t) and let ' be the resulting remaining job sizes. Let ' be the optimal residual schedule for '; thus we have f(') = ^_'('). Let  be the schedule that first has ” for t units of time and then exactly follows '. Since  is a valid residual schedule for remaining sizes , we have f() ≤^_(). Therefore, 


    f(') - f() ≥^_'(') - ^_() = -  t ∑_x_j>0w_j

As above, the equality holds as each job j's completion time (such that x_j > 0) differs exactly by t in the two schedules  and '.
This implies GD decreases the residual objective by at most t ∑_x_j>0w_j. Thus we have () =  - ∑_x_j>0w_j, as desired.


The next lemma demonstrates that we can implement GD more efficiently by following the optimal residual schedule until a new job arrives. Upon a new job arrival, we recompute a new optimal residual schedule. The lemma is unnecessary if we are willing to compute the optimal residual schedule at every time step.


    
    Let  denote the optimum residual schedule for remaining sizes (t). Suppose no jobs arrive during the time interval [t, t']. Then, we can assume wlog that GD processes jobs at rates (t̃) at each time t + t̃ for all t̃∈ [0, t' - t].


    The proof of this lemma is implicit in that of Lemma <ref>. Eqn. (<ref>) shows that processing along , until a job is completed, is as effective as GD, which by definition is the most effective in decreasing the residual objective. Note that the remaining schedule must be an optimum residual schedule for the rest of the jobs. Then, we can recurse on the remaining sizes, until time t' when a new job arrives and we  recompute the optimum residual schedule.
   


The following lemma bounds the potential change when a job arrives or is completed. This is where we use supermodularity.


    
    If Φ(t) changes discontinuously due to a job's arrival or completion, the change is non-positive.


    If there is no arrival and completion, thanks to 
    Lemma <ref>, it is straightforward to see Φ(t) is continuous in t and differentiable.

    First, we observe that job completion in A's schedule or the optimum solution's schedule has no effect on f and therefore on Φ(t). This is because once a job j's remaining size becomes 0, then the residual optimum schedule does not process it. Thus, we only need to consider job arrival.
    
    Suppose a new job j arrives at a fixed time t. For brevity, we drop t in the following. Let _j^A denote the unit vector that has 1 only the position corresponding to j in A's schedule. 
        Define _j^O analogously for the other copy of j in O's schedule. Here j^A and j^O refer to j's copy in the schedule of A and O, resp.  Dropping t from the notation for brevity, f(^A  ||  ^O) increases by: 
    
    f(^A ||  p_j _j^A ||  ^O  ||  p_j  _j^O) - f(^A ||  ^O)
        = g̅_(A ∪ j^A ∪ O ∪ j^O) - g̅_(A ∪ O)

where = ^A ||  p_j  _j^A ||  ^O  ||  p_j  _j^O. 
Recall that the function g̅_(S) computes f assuming that each  j' ∈ S has size ·_j' and every job not in S has zero size. Notably, we view f as a set function g̅ by fixing each job's (remaining) size. 
In the remaining proof, we use g instead of g̅_ for notational brevity. 
    
    By supermodularity of g (due to the theorem condition), we have, 
    
    g(A ∪ j^A ∪ O ∪ j^O) - g(A ∪ O)  
    ≥     g(A ∪ j^A ∪ j^O) - g(A) 
    
        =       g(A ∪ j^A ∪ j^O) - g(A ∪ j^A ) + g(A ∪ j^A) - g(A) 
    ≥     g(A  ∪ j^O) - g(A) + g(A ∪ j^A) - g(A) 
    
        =      2 (g(A  ∪ j^A) - g(A)),

where the last inequality follows from the fact that j^O and j^A both have the same size p_j when j arrives.

Now, we shift to bounding the change of f(^A), which increases by exactly

    f(^A ||  p_j _j^A) - f(^A)
        = g(A ∪ j^A) - g(A)


Therefore, Φ(t)'s change is at most
2/( g(A ∪ j^A) - g(A) - 
1/2· 2(g(A ∪ j^A) - g(A))) = 0, as desired.





    
    Consider any time t when no job arrival or completion occurs. If A and O are given s-speed and 1-speed respectively,  / t f(^A(t)  ||  ^O(t))  ≥ - (s + 1) ( W^A(t) + W^O(t) ).


    We observe that processing jobs in A and O can be thought as a feasible schedule with speed s+1 (A and O are given speeds s and 1 respectively). How much can one decrease f(^A(t)  ||  ^O(t)) when given s+1-speed? Lemma <ref>, together with Claim <ref>, implies that even GD, which is the most effective in decreasing the residual objective, can decrease at a rate up to the total weight of all jobs (of non-zero remaining sizes) times s+1 when given s+1 speed. Thus, the lemma follows.     
       



    
    Consider any time t when no job arrival or completion occurs. Then, / tΦ(t) ≤ -W^A(t) + (1 + 2/) W^O(t) when GD is given 1+-speed.


    From Lemmas <ref> and <ref>, we have
    / tΦ(t)  = / t2/(f(^A(t)) -  1/2f(^A(t) || ^O(t)))
    ≤2/ ( - sW^A(t) + s+1/2 (W^A(t) + W^O(t)))  = -W^A(t) + (1 + 2/) W^O(t), where s = 1+.


By Lemma <ref> and the fact that Φ(T) = Φ(0) = 0, we have ∫_t=0^∞/ tΦ(t)  t ≥ 0. By Corollary <ref>, we know that ∫_t=0^∞ W^A(t)  t ≤2 +  /∫_t=0^∞ W^O(t)  t. Since the LHS and RHS are the total integral weighted flow time of GD and the optimum schedule respectively (Proposition <ref>), we have Theorem <ref>.
























 §.§ Proof of Theorem <ref>




We continue to use the same notation ^A(t) and ^O(t) as we used in the previous section. We use the same meta-potential function. But, here we use fractional completion time for the residual optimum, so we have f() := min_^_() (see Eqn. (<ref>)). 





    Φ(t) = 2/(f(^A(t)) - 1/2f(^A(t) || ^O(t)))



As before, each job j has two distinct copies, which each appear in ^A and ^O. 


We first establish f's supermodularity. 


    
    f() := min_^_() is (discrete-)supermodular.


Showing the lemma is equivalent to showing - f() is submodular. Then, the objective in Eqn. (<ref>) becomes 
max∑_j ∈ A(t)∫_t̃≥ 0 - w_j/p_jt̃· z_j(t̃) t̃. This is equivalent to max∑_j ∈ A(t)∫_t̃≥ 0 (B - w_j/p_jt̃)  z_j(t̃) t̃ for any constant B > 0 due to the constraint ∫_t̃≥ 0 z_j(t̃) t̃ = x_j
for all j ∈ A(t); also adding a constant does not change a function's submodularity.  Further, if we let B be a sufficiently large constant, we obtain the following equivalent formulation. 

    max∑_j ∈ A(t)   ∫_t̃≥ 0(B -  w_j t̃/p_j)  z_j(t̃) t̃   
    ∫_t̃≥ 0 z_j(t̃) t̃   ≤  x_j   ∀ j ∈ A(t) 
    (t̃)    ∈  ∀t̃≥ 0

Note that although the first constraint does not require equality, due to the big constant B, the optimum solution to the above LP must process j to the full x_j units. 
 
We now create a valuation function v_t̃ for each time t̃.


    v_t̃((t̃)) := max_0 ≤≤(t̃), ∈∑_j ∈ A(t)(B -  w_j t̃/p_j)  y_j

In other words, here we view each time t̃ as an agent[Technically, achieving this result requires discretizing the time horizon into a finite set of sufficiently small unit times and then taking the limit. However, to maintain clarity in the presentation, we omit this technical detail as it is straightforward. ] with valuation function v_t̃ and view each job j's size/processing as a divisible resource, which exists by x_j units. When agent t̃ receives processing units (t̃), it can process each job j and it would like to maximize an objective linear in  subject to ∈ and ≤ z(t̃).

By the precondition of the theorem, v_t̃ is LS. Then max LP objective is equivalent to 

    max∫ v_t̃ (z(t̃)) t̃∫_t̃≥ 0 z(t̃) t̃≤

Since this is a convolution of LS valuations, thanks to Lemma <ref>, we have the max LP optimum is LS w.r.t. . From Lemma <ref>, we know that it is submodular. 
Thus, we have shown f is supermodular. 
It is an easy exercise to show that this means f's discrete-supermodularity (see Definition <ref>) using the fact that _A ∪ B⊙ = (_A⊙) ∨ (_B⊙) and _A ∩ B⊙ = (_A⊙) ∧ (_B⊙).




The remaining analysis is almost identical to the proof of Theorem <ref>. 
We start the analysis by considering Φ(t)'s discontinuous changes. The proof of the following lemma is identical to that of Lemma <ref>, which crucially used  f's supermodularity. 



    
    If Φ(t) changes discontinuously, the change is non-positive.

    
Let W̃^A(t) := ∑_j ∈ A(t)w_j/p_jp^A_j(t) denote the total fractional weight of jobs at time t in A's schedule. Let W̃^O(t) denote the corresponding quantity in O's schedule. We will assume that GD follows the optimum residual schedule and  show that no algorithm can decrease the residual optimum  more effectively than GD.[In the proof of Theorem <ref> we defined GD to be the most effective algorithm for decreasing the residual optimum, and we showed following the residual optimum schedule is as effective as GD. We make this small change, as we now know GD is really nothing but following the residual optimum.]

The following lemma quantifies the decrease rate of the (fractional) residual optimum. 


    
    For any time t when no job arrival or completion occurs, we have / t f(^A(t)) = - s W̃^A(t) when we run GD with s speed. Furthermore, for any algorithm with s speed, we have / t f(^A(t)) ≥ - s W̃^A(t).


    Fix a time t and consider how much 
     f(^A(t)) changes during [t, t+  t) when we run GD with s-speed. 
         Let = min_'_^A(t)('). Note that j contributes to the objective f(^A(t)) by ∫_τ≥ 0w_j/p_jτ z_j(τ) τ.
    GD schedules (τ), τ∈ [0, s  t) during time interval [t, t+  t) as it is given s speed. Note that 
    (τ), τ∈ [s  t, ∞) is a feasible schedule (with 1-speed) for remaining job sizes ^A(t) - (s  t) where (τ') := ∫^τ'_τ”≥ 0(τ”) τ”. Therefore, ', where  '(τ) = (s  t+ τ), is a feasible solution to _^A(t) - (s  t). 
       
   
    Thus, f(^A(t)) decreases by
    
    f(^A(t)) - f(^A(t)- (s  t)) 
    ≥    f(^A(t)) - _^A(t) - (s  t)(') 
    
        =     ∑_j (∫_τ≥ 0w_j/p_jτ z_j(τ) τ - ∫_τ≥ s  tw_j/p_j (τ - s  t) z_j(τ) τ) 
    ≥     s  t ∑_j w_j/p_j∫_τ≥ s dt z_j(τ) τ = s  t (W̃^A(t) - ∑_j w_j/p_j Z_j(s  t)),

    which implies / t f(^A(t)) ≤ - s W̃^A(t). 

    
    Similarly, we can show the other direction. 
    Consider any feasible s-speed processing ' during the time interval; so, j is processed by Z'_j units. Let = min_'_^A(t) - '(') denote the optimum residual schedule for the remaining job sizes. 
    Let ' ∘ denote the 1-speed schedule where we first process ' for s  t time units and subsequently schedule . Note that ' ∘ is a feasible solution to _^A(t). Therefore, f(^A(t)) decreases by
    
    
    f(^A(t)) - f(^A(t)- ') 
    ≤    _^A(t)(' ∘) - _^A(t)- '() 
    ≤    ∑_j (∫_τ≥ 0w_j/p_j (τ + s  t) z_j(τ) τ - ∫_τ≥ 0w_j/p_jτ z_j(τ) τ) + ∑_j  t w_j/p_j Z'_j
    ≤     s  t   ∑_j w_j/p_j∫_τ≥ 0  z_j(τ) τ +   t ∑_j  w_j/p_j Z'_j
        
        =        s  t W̃^A(t) +   t ∑_j  w_j/p_j Z'_j,

    
    which implies  / t f(^A(t)) ≥ - s W̃^A(t), as desired. 
    



This lemma allows us to  bound the continuous change of the second term of Φ(t). The proof is essentially identical to that of Lemma <ref>: it follows from the observation that we can view A and O's combined processing as a s+1-speed schedule and the residual objective can change at a rate up to the total fractional weight of jobs in the system, times s+1. 



    
    Consider any time t when no job arrival or completion occurs. If A and O are given s-speed and 1-speed respectively,  / t f(^A(t)  ||  ^O(t))  ≥ - (s + 1) ( W̃^A(t) + W̃^O(t)).


Combining the two lemmas we obtain the following corollary. 


    
    Consider any time t when no job arrival or completion occurs. When GD is given 1+-speed, we have d/dtΦ(t) ≤ -W̃^A(t) + 2 +  /W̃^O(t).


By Lemma <ref> and the fact that Φ(T) = Φ(0) = 0, it must be the case that ∫_t = 0^∞/ tΦ(t)  t ≥ 0. By Corollary <ref> we know that
∫_t = 0^∞W̃^A(t)  t ≤2 +  /∫_t = 0^∞W̃^O(t)  t where the LHS and RHS are exactly the total weighted fractional flow time of GD and the optimum schedule (Proposition <ref>). Thus, we have Theorem <ref> for total fractional weighted flow time. Lemma <ref> allows us to obtain an algorithm that is (1+)-speed O(1 / ^2)-competitive for the integer objective. 












 §.§ Proof of Theorem <ref>


This section is devoted to proving Theorem <ref>. 
The high-level idea is to show that when we take the feasible processing rate view, we satisfy the condition of Theorem <ref>, i.e.,  
v() := max_0 ≤≤, ∈· is  linear substitute. Note that ∈ if and only if _j = u_j(_j) for all j for some non-negative vectors {_j}_j ∈ J such that ∑_j _j ≤. 

For any price vector , let () denote the unique solution to: 


    max_'∑_i ∈ J   (c_i - q_i) x'_i 
    '    ∈


To see that this is well defined, take the resource view of the CP. Recall in the resource view, each job i is associated with a valuation function u_i and the divisible resources [0, 1]^d are allocated to the jobs. If _i denotes the resources job i receives, we have the following equivalent CP.


    max∑_i ∈ J   (c_i - q_i) u_i(_i) 
    ∑_i ∈ J_i    ≤
    _i    ≥0  ∀ i ∈ J


It is straightforward to see that this CP has a unique solution due to the theorem condition that u_i is strictly concave for all jobs i. 


Without loss of generality, we assume <. This is because jobs i with c_i - q_i ≤ 0 do not play any roles and therefore we can pretend that they do not exist. Now consider the Walrasian market where each job/agent i has a valuation function (c_i - q_i) u_i for divisible resources [0, 1]^D. Because u_i is LS for all i, which is a precondition of Theorem <ref>, (c_i - q_i) u_i is LS for all i (LS is closed under a positive scalar multiplication). 
Thus, the CP formulates the social surplus maximization problem where all agents have LS valuations. In the following  and ' are uniquely defined as u_i is assumed to be strictly monotone and strictly concave. 



    
    
    Consider any ≤' ∈^|J|. 
    Let  be the equilibrium price vector for the market with valuations (c_i - q_i) u_i, i ∈ J along with divisible resources [0, 1]^d. Similarly, let ' be the  equilibrium price vector for (c_i - q'_i) u_i, i ∈ J. We have ' ≤.


    To prove this lemma, we use the tatonnement process described in <cit.>.[Although the process is described for indivisible resources that exist in multiple units, the same proof extends to divisible resources. The proof can be much simplified if we assume valuation functions are strictly concave, as shown in <cit.>.]
    The tatonnement process is governed by a price vector (τ); the vector monotonically changes as τ increases.     We say that all resources are under-demanded[The over-demanded case is symmetric.] under the current price vector ” if there exists an allocation ” that maximizes everyone's (here, every job i's) quasi-linear utility and ∑_i ”_i ≤. Here, if job i's utility is (c_i - q_i) u_i, then ”_i ∈D((c_i - q_i) u_i, ”).
    For brevity, we will equivalently say that ” is an under-demand price vector. 
    It is shown in <cit.> that starting with any under-demand price vector (0), we can monotonically decrease (τ) to an under-demand equilibrium price, which yields the maximum social surplus.
    
    Let  be the unique allocation achieving the unique equilibrium with the price vector .
    Define ' analogously for (c_i - q_i')u_i with the price vector .
   
    Since for all i, c_i - q_i ≥ c_i - q_i' and _i' ∈D((c_i - q_i') u_i, ) = D( (c_i - q_i) u_i,  c_i - q_i/ c_i - q_i' ), we have  _i' ≤_i due to the first property of Theorem <ref>. Thus, ∑_i '_i ≤, meaning  is an under-demand price vector when each i has valuation (c_i - q'_i)u_i. Thanks to the above tatonnement process, we conclude ' ≤. 




Now we are ready to prove that v() is LS. 
Say q'_j > q_j and q'_i = q_i for all i ≠ j, so we only increased job j's price. 
Consider any i ≠ j. We use  and ' as we defined in the proof of Lemma <ref>. Since u_i is strictly concave, we have, 

    {_i}   =  D((c_i - q_i)u_i, ) = D(u_i,  / (c_i - q_i)) 
    {'_i}   =  D((c_i - q_i') u_i, ') = D((c_i - q_i) u_i, ') = D(u_i, ' / (c_i - q_i))


From Lemma <ref>, we know  ' ≤. Thus, due to the second property stated in Theorem <ref>, we have u_i(_i') ≥ u_i(_i). 

Knowing that x_i() = u_i(_i) and x_i(') = u_i(_i'), we conclude 

    x_i(') ≥ x_i()





    
    If > 0, then the demand set 𝒟(v, ) is a singleton set. Further, we have 𝒟(v, ) = {()}. 


The quasi-linear utility, v('
) - ·' is maximized only when ' ∈ since > 0. Then, the quasi-linear utility maximization can be written as max_'·' - ·' s.t. ' ∈ which has a unique solution as discussed above. The solution is () by definition. 


Thus, if > 0, then we have ' > 0 as well. Due to Lemma <ref> and Eqn. (<ref>), we have shown that v is LS. Therefore, we have Theorem <ref> from Theorem <ref>.

We extend the proof to an arbitrary ≥ 0.
Let J^0 denote the set of jobs j with q_j = 0, and J^+ the other jobs. It is an easy exercise to show that 

    D(v, ) = {() + ∑_j ∈ J^0λ_j _j    |  λ_j ≥ 0  ∀ j ∈ J^0}.

In other words, the quasi-linear utility is maximized by purchasing any amount of free jobs on top of (). Consider any ∈D(v, ) and increase job j's price, so we have ' such that q'_j > q_j and q'_i = q_i for all i ≠ j. For any i ∈ J^0 such that i ≠ j, it is trivial to see that we can find '  ∈D(v, ') such that x'_i ≥ x_i as job i is free. If i ∈ J^+, we have x_i(') ≥ x_i() = x_i, where the inequality follows from Eqn. (<ref>) and the equality follows from Eqn. (<ref>) with the facts that  , () ∈D (v, )  and i ∈ J^+.








    


§ APPLICATIONS OF THE THEOREMS

    

In this section, we discuss some problems captured by our theorems. 
See Section <ref> for their definition.




 §.§ Matroid Scheduling


We can formulate the matroid scheduling problem as an instance of the PSP as follows: 


    = { |  ∑_j ∈ S z_j ≤ r(S)   ∀ S ⊆ J }


where r is the rank function of the given matroid M = (J, I) and z_j is the processing rate of job j. For a cost vector , v̅(_S) = max_≤_S, ∈ 2^J, ∈· is equivalent to the weighted rank function of a matroid, which is known to be GS (Section <ref>).
Note that v̅(_S)  = v(_S)  for all S ⊆ J because the polytope  is integral, where  v() = max_≤, ∈· (see Theorem <ref>).


To show v is LS, we prove that the concave closure of v̅ is equivalent to v. For the concave closure definition, see Theorem <ref>. Note that here we used v̅ to distinguish the discrete valuation from the continuous valuation v. 


    For ∈ [0,1]^J, v() = v̅^+().


    First, we show the “≤" direction. Let ∈ such that v() = v(). 
    Since  is integral, we can express  as a convex combination of the subsets of J, so = ∑_S ∈ℐλ_S ·_S, where ∑_S  ∈ℐλ_S = 1. Then, v() = · =  ∑_S ∈ℐλ_S (·_S) = ∑_S ∈ℐλ_S  v̅(_S) ≤ v^+().

    
    To show the other direction, let v̅^+() = ∑_S v̅(_S) λ_S for some   {λ_S}_S ⊆ J with ∑_S λ_S = 1 and ∑_S λ_S _S =. Let π(S) be S' ⊆ S such that _S'∈ and 
    v̅(_S') = v̅(_S). We then have
    
    v̅^+() = ∑_S v̅(_π(S)) λ_S = ∑_S   λ_S  ·_π(S)


    Let ' := ∑_S λ_S_π(S). Note that ' ≤. Further, ' ∈ due to 's integrality. By definition of v, we know v is monotone. Thus, we have, 
    
    v() ≥ v(') = ·' = ∑_S λ_S  ·_π(S)

    From Eqn. (<ref>) and (<ref>), we conclude v() ≥v̅^+(), as desired. 
   


Since v̅^+ is LS, so is v.  Therefore, Theorem <ref> establishes GD as a scalable algorithm. 
Finally, if  {λ_S }_S ∈ℐ is the convex combination of independent sets that achieves v^+(), we can implement our algorithm by preemptively scheduling each independent set S in proportional to λ_S.




 §.§ Generalized Flow Scheduling




Recall that we are given a network G=(V,E), where J ⊆ V is the set of source nodes. Arc e has capacity u_e and flow gain factor γ_e; a flow of value f becomes γ_e f after flowing through e. 
Job j gets processed at a rate equal to its (outgoing) net flow. Formally, node v has excess capacity b_v. Sources have non-negative excess capacities. A job j gets processed at a rate of z_j, when its net flow is z_j for  ∈, which is defined as follows.


    =   = ⟨∑_w (f_jw - γ_wj f_wj)  ⟩_j  ∈ J |  ∑_w (f_vw - γ_wv f_wv)≤ b_v  ∀ v ∈ V; f_e ≤ u_e ∀ e ∈ E; ≥ 0


Theorem <ref> shows v() = max_∈· is LS. Note that our network can ensure ≤ by setting the excess capacity of the node that represents job j to be x_j. Thus, we immediately have a scalable algorithm due to Theorem <ref>.




 §.§ Speed-up Curves on Partitioned Resources


We consider this problem from the Resource View. Then we need to show that the utility u_j is linear-substitute and satisfies two desired properties in Theorem <ref>. Without loss of generality, we can assume the utility is determined by only one univariate function that is u_j() = g(∑_d∈ [D] a_d x_d). We drop j for brevity henceforth.

We begin by showing a simple greedy algorithm being optimal. The proof follows from a simple swapping argument. 


    
    For any price vector  on resources, the greedy algorithm selects elements fractionally in decreasing order of a_d / q_d until no marginal increment, finds a solution maximizing the quasi-linear utility, i.e., a solution in  D(u, ).


    Fix some price vector  on resources.  Assume that a_1 / q_1 ≥ a_2 / q_2 ≥ ...≥ a_D / q_D. Suppose we have an optimum solution  where  x_i < 1 and x_j > 0 for some i < j. Then, we maximally increase x_i by a_j δ / a_i and decrease x_j by δ for some δ 
 >0
     until x_i becomes 1 or x_j becomes 0. This    preserves the value of ∑_d a_d x_d without increasing ·. By repeating  this, we have the lemma. 


First, we prove that u satisfies linear-substitute. Although the claim is known to be true (see Section 
 5 in <cit.>), we include it as it is a nice warm-up before proving the subsequent claims. 

  
    u is linear-substitute.


    Consider the greedy algorithm in Lemma <ref>. Now we increase the price of resource d. In the new greedy order, the resource d can only be considered later; other elements keep the same relative order. Thus ^*_i can not decrease for all i ≠ d because they are processed earlier than the original greedy order. Therefore, we have the claim.



The following claim shows that when we increase the price vector  simultaneously for each coordinate at the same scale, u can only demand less.


    For any ∈D(u, ) and λ≥ 1, there exists ' ∈D(u, λ) such that ≥'.


    Consider the greedy algorithm in Lemma <ref>. Note that increasing the price vector  to λ does not change the order of a_d / q_d. Thus the stopping point in the execution of the greedy algorithm comes earlier as the marginal increment becomes zero with fewer resources in the order, which gives the proof.



Further, we show that when we increase the price vector , the utility would not increase.


    For any ∈D(u, ) and ' ≥, there exists ' ∈D(u, ') such that u() ≥ u(').


    For the sake of contradiction, suppose u() < u (').  
Let ' be the solution constructed by the greedy algorithm described in the proof of Lemma <ref> with price vector '. Define  analogously with . Because of the assumption u() < u (') and g's monotonicity, it must be the case that 
∑_i a_i y_i < ∑_i a_i y_i'. Let ” be the “prefix” of ' such that z :=∑_i a_i y_i = ∑_i a_i y_i”. In other words, we run the greedy with ' but stop when  z  = ∑_i a_i y_i”. 
Let k be the smallest such that y_k' > y_k”. The greedy with respect to ' further increases ” since the marginal gain g(z +  a_k) - g(z) - '_k > 0 for a sufficiently small >0. Therefore, if _k < 1, the greedy must have continued increasing  since g(z +  a_k) - g(z) -  q_k ≥ g(z +  a_k) - g(z) - '_k > 0. Since the greedy with respect to  considers resources in the order of 1, 2, …, it means _1 = _2 = … = _k = 1; yet ”_k < 1 and ”_k+1 = ”_k+2 = … = ”_D  = 0. This is a contradiction to
∑_i a_i y_i < ∑_i a_i y_i'.


Finally, we discuss why it is wlog to assume that u is strictly monotone and strictly concave. To obtain a strictly concave function that is arbitrarily close to u, we replace each x_d with x_d^1 - δ for an arbitrary small δ > 0. Further, we replace g with a strictly monotone function that is arbitrarily close to g. It is an easy exercise to show this new function is strictly concave and arbitrarily close to the original function u on [0, 1]^D. We then pretend an infinitesimal unit  of each resource as a distinct item and order these infinitesimal-sized items in decreasing order of 
a_d (( k)^1 - δ - ((k-1))^ 1 - δ) / (p_d ), which corresponds to the effectiveness of  the k-th -sized copy of resource d. It is straightforward to check that the whole analysis remains unchanged. Further, if u does not depend on some resources, then for each of such resources d we can add λ_d x_d^1-δ for a sufficiently small λ_d > 0, so this additional term essentially has no effect on u while ensuring u being strictly monotone. 

Thus, this application admits 
 a scalable algorithm due to Theorem <ref>. 




 §.§ Unrelated Machines for Unweighted Jobs

    

In this section we show how to obtain a (1+)-speed O(1 / )-competitive algorithm for total unweighted flow time using gradient descent; the weighted case is presented in the following section. Our algorithm is migratory, unlike the algorithms in <cit.>. (We also reproduce the non-migratory result in <cit.> in  Section <ref>, focusing on supermodularity and gradient descent.) 

Unfortunately, we can not directly use Theorem <ref> for the following reason: the problem we consider allows migration of jobs across machines. The residual optimum of a migratory schedule does not seem to be LS. Thus, we use 
the non-migratory residual optimum, which turns out to be GS. Interestingly, our resulting gradient descent algorithm is migratory. Nevertheless, the analysis will be very similar to the proof of Theorem <ref>. Thus, we will adopt the same notation throughout this section.


We first describe the residual optimum for this problem. Let f() denote (the cost of) the min-cost non-migratory schedule of jobs, where each job j has (remaining) size x_j. It is well known that it can be computed by min-cost bipartite matching. For completeness, we describe it here: Consider a bipartite graph G = (J, M'; E) where there is a unique node,  indexed by (i, k), for each pair of machine i and k ∈_> 0. There is an edge between j ∈ J and (i, k) ∈ M'. Choosing the edge means scheduling  job j on machine i in the k-th reverse order non-preemptively, thus the edge has cost k · p_ij, where p_ij = x_j / λ_ij. Intuitively, this means there are k jobs behind job j on the machine, including itself—thus j delays k jobs—when following SRPT on each machine. The residual optimum f() is the min cost of a bipartite matching for this instance. 



 
    
    g̅_(J') := f(⊙_J') is  (discrete)-supermodular.
 

    From Section <ref>, we know that maximum weight bipartite matching is GS. 
    Therefore, - g̅_ is GS and submodular. 


As before, we use () to denote the max decrease rate of the residual optimum. We will see that following the optimum residual schedule until a new job arrives is as effective as the true GD; that is, it decreases the residual optimum at a rate equal to (). 


Since the analysis is very similar to  the proof of Theorem <ref>, we only highlight the differences. We use the same potential function. Lemma <ref> gives supermodularity of the residual optimum. Thus, we can show all discrete changes of Φ is non-positive following the same argument in the proof of Lemma <ref>.


    
    When the residual optimum is f(), we have  () = -∑_x_j>0 1. 


    Proving () ≤ -Σ_x_j>0 1 is identical to the first part proof of Lemma <ref>. In fact, we can decrease f() at a rate of at least Σ_x_j>0 1 by following the residual optimum schedule. 
 
Showing the other direction needs special care because while the residual optimum schedule is non-migratory, changing the job assignment could help decrease the residual optimum. Assume wlog that > 0, because we can ignore jobs j such that x_j = 0.
Suppose GD processes j(i) on machine i for a sufficiently small unit time t, so no job completes during the time slot. Let ' be the resulting remaining job sizes and σ' be the optimal non-migratory schedule for ', where j is scheduled on machine ψ(j). Let σ be the non-migratory schedule obtained from σ' by increasing each job's remaining size from x'_j
to x_j, without changing the assignment ψ and the job ordering on each machine. So, σ is a feasible non-migratory schedule for , but not necessarily optimum. Let (σ) denote the total completion time of schedule σ. Clearly we have,


    () · t ≥(σ')  - (σ).

Thus, it suffices to lower bound (σ')  - (σ). For notational brevity, let x'_ij := x'_j / λ_ij, which is j's processing time on i when its remaining size is x'_j. Similarly, let x_ij := x_j / λ_ij. Define P_i, <  k := ∑_j': x'_ij' < x'_ik x'_ij' to be the total remaining processing time of jobs smaller than job k on machine i w.r.t. ' in σ', breaking ties in an arbitrary but fixed order. Let N_i, ≥ k := ∑_j': x'_ij'≥ x'_ik 1 denote the number of jobs of  remaining sizes no smaller than job k on machine i w.r.t. ' in σ'.

Since j(i) gets processed on machine i, we have x_j(i) - x'_j(i) = λ_i, j(i) t. The job j(i) is on machine ψ(j(i)), and the number of jobs behind it[Note that on each machine i jobs are ordered following the SRPT order, i.e. in decreasing order of x_ij.], including itself, is exactly N_ψ(j(i)), ≥ j(i). Thus, due to  x'_j(i) increasing to x_j(i), j(i)'s contribution to (σ') - (σ) is exactly,

    N_ψ(j(i)), ≥ j(i) x'_ψ(j(i)),j(i) - N_ψ(j(i)), ≥ j(i) x_ψ(j(i)), j(i)
        = - N_ψ(j(i)), ≥ j(i)λ_i, j(i)/λ_ψ(j(i)), j(i) t


Therefore, we have

    () ≥ - ∑_i N_ψ(j(i)), ≥ j(i)λ_i, j(i)/λ_ψ(j(i)), j(i) t


We complete the proof by showing 

    N_i ≥ N_ψ(j(i)), ≥ j(i)λ_i, j(i)/λ_ψ(j(i)), j(i)

for all i, 
where N_i := |ψ^-1(i)| is the number of jobs assigned to machine i. To see this, observe the following: 

    P_i, <  j(i) + N_i, ≥ j(i)x'_j(i)/λ_i, j(i)≥
    P_ψ(j(i)), <  j(i)  + N_ψ(j(i)), ≥ j(i)x'_j(i)/λ_ψ(j(i)), j(i),

This is because the LHS and RHS measure the increase of the objective due to j(i)'s presence on machines i and  ψ(j(i)), respectively (in other words, the LHS is the increase of the residual objective on machine i 
when we move j(i) from ψ(j(i)) to i, and the RHS is the decrease of the residual objective on machine ψ(j(i)) for that move): The first term is j(i)'s start time and the second is the number of jobs delayed by j(i), including itself, multiplied by j(i)'s remaining size on the machine. Thus, the inequality is a necessary condition for σ' being the optimal residual schedule for '.

Multiplying both sides in Eqn. (<ref>) by λ_i, j(i)/x'_j(i) = 1/x'_i,j(i), we have

    P_i, <  j(i)/x'_i, j(i) + N_i, ≥ j(i)≥P_ψ(j(i)), <  j(i)/x'_j /λ_i, j(i)  + N_ψ(j(i)), ≥ j(i)λ_i, j(i)/λ_ψ(j(i)), j(i).


For the first term, we have P_i, <  j(i)/x'_i, j(i) = ∑_j': x'_ij' < x'_i, j(i) x'_ij' / x'_i, j(i)≤∑_j': x'_ij' < x'_i, j(i) 1. Thus, it is at most the number of jobs that have smaller processing times than j(i) on machine i. Thus, the LHS is at most the number of jobs assigned to machine i, i.e., N_i, as desired. 




As mentioned in the above proof, following the non-migratory residual optimum schedule decreases the residual as much as GD. Further, it is an easy exercise to show that we do not have to compute a residual optimum until a new job arrives. All the remaining analysis remains the same and is omitted. 





 §.§ Unrelated Machines for Weighted Jobs

    

In this section, we extend the GD algorithm to handle weighted jobs and give an algorithm that is (1+)-speed O(1 / ^3)-competitive algorithm for total weighted flow time. One may try the previous residual LP (Eqn. (<ref>)) where 

    
    = { z_j(t̃) = ∑_iλ_ij y_ij(t̃)   |  ∑_i y_ij(t̃) ≤ 1  ∀ j, t̃ ;  ∑_j y_ij(t̃) ≤ 1  ∀ i, t̃}


Unfortunately, this objective does not seem to be LS. 
Instead, we consider essentially the same LP that was used in <cit.> for their dual fitting analysis. 
However, our algorithm is very different from the immediate-dispatch algorithm that was given in  <cit.>. 
For notional simplicity, we may use p_ij := p_j / λ_ij to denote the processing time of job j on machine i when j is processed on machine i only. 




    f() := min∑_i,jw_j λ_ij/p_j∫_t̃≥ 0t̃· z_ij(t̃) t̃_(*)   + ∑_i,j w_j ∫_t̃≥ 0 z_ij(t̃) t̃_(**)
    ∑_j z_ij(t̃)    ≤ 1   ∀ i, t̃
    ∑_i∫_t̃≥ 0λ_ij z_ij(t̃)t̃   = x_j   ∀ j


This new objective will be shown to be supermodular from the LS property (see Lemma <ref>). Notice that this LP does not force a job to be processed on at most one machine; thus (t̃) may not be a feasible schedule. For this reason, we can not directly apply the GD algorithm in Section <ref>, which schedules (t̃ = 0). 

 To handle this issue, we consider the following approximate GD: For each machine i, we only process one unit of jobs that appear the earliest in (t̃), ensuring that each job j gets processed up to the fraction of the job assigned to the machine. Formally, 
 let t̃_i be the earliest time that ∑_j ∫_t̃=0^t̃_iz_ij(t̃)/p_ijt̃ = 1. Then we process ẑ_ij := ∫_t̃=0^t̃_iz_ij(t̃)/p_ijt̃ fraction of job j on machine i.
We continue this schedule until the fraction of a job on some machine is completed. For brevity, we may call this approximate GD as GD. 


    If we use the true GD algorithm, which decreases the residual optimum objective the most, we can still show the same guarantee. However, for the sake of analysis, we will consider the approximate GD. 


We first verify that   is a feasible schedule. By definition of the algorithm, we have ∑_jẑ_ij≤ 1 for all i. This, together with the following claim, shows that ẑ_ij is a fractional matching between jobs and machines. Since a fractional bipartite matching can be expressed as a convex combination of integral matchings, we have that ẑ_ij is indeed a feasible schedule. 


    For any job j, we have ∑_iẑ_ij≤ 1.


    From the second constraint of LP, we have

        
    ∑_iẑ_ij = ∑_i ∫_t̃=0^t̃_iz_ij(t̃)/p_ijt̃≤∑_i ∫_t̃≥ 0^t̃_iλ_ijz_ij(t̃)/p_jt̃ = x_j/p_j≤ 1.



For simplicity, we  assume wlog that ∑_i ẑ_ij = 1 and ∑_j ẑ_ij = 1, by adding  0 weight jobs.





For the analysis, we use the following potential function.
    
    Φ(t) = 2/( f(^A(t)) -  f (^A(t)   ||  (1/ - 1)^O(t)))
 
Here we note that f (^A(t)   ||  (1/ - 1)^O(t))
is the optimum objective of  when we have  one copy of each job j in A(t) with remaining size p^A_j(t) and (1 /  - 1) copies of each job j in O(t), each with remaining size p^O_j(t). 





  §.§.§ Analysis Overview


Before diving into the analysis, we first provide a high-level overview. Since the LP solution does not directly give us a time-indexed feasible schedule, we compromised true gradient descent. If possible, it would be the best for the algorithm to process exactly what the LP solution processes at time t̃ = 0. Unfortunately as discussed before, this may not be feasible. 

To intuitively understand our algorithm, consider a single machine i where jobs 1, 2, 3, … are processed in this order, each by a half fraction. For simplicity, let us drop i from the notation. Then, the LP solution on the machine is processing j for p_j / 2 time steps. As mentioned before, fully processing job 1 on the machine may result in an infeasible schedule if job 1 is scheduled before other jobs on another machine in the LP solution. Our algorithm processes job 1 and job 2, each by half on the machine (these two jobs are the first unit fraction of jobs), to ensure a feasible schedule. This is surely not so effective as fully processing job 1 in decreasing (*). However, for all jobs except 1 and 2, our algorithm is equally effective! Further, for the deficit due to jobs 1 and 2, (**) comes to rescue. So, if W̃_(1) is the total fractional weight processed by our algorithm, and we let W̃_(2) be the other total fractional weight, our algorithm gets W̃_(1) credit from (**) and W̃_(2) credit from (*). Thus, f(^A(t))) decreases at a rate of at least W̃_(1) + W̃_(2), which is the total fractional weight of the remaining jobs in our algorithm's schedule. 

To show the algorithm is scalable, we create (1/ - 1) copies of each job in the adversary's schedule and due to this we lose another 1 / factor in the competitive ratio, but this is a minor technicality. The critical observation is that the approximate GD is as effective as GD with the aid of the decrease of (**). 

As before we will consider the discrete changes and continuous changes separately. 




  §.§.§ Analysis: Discrete Changes


    
The proof of discrete changes of Φ is very similar to Lemma <ref>, so we only highlight the differences. First, we will use generalized flow to show the supermodularity of our new residual objective. 


    
    f(x) is (discrete-)supermodular.


    We follow the same strategy as we used to prove Lemma <ref>. Consider the following valuation
    
    v_t̃((t̃)) := max∑_i,j(B λ_ij - w_j t̃/p_ij - 1 ) z_ij s.t. 0 ≤∑_i λ_ij z_ij≤ x_j(t̃), ∑_j z_ij≤ 1

    for each time t̃. It is easy to see that the LP objective by flipping the sign and adding a big constant is equivalent to 
        
    max∫_t̃≥ 0 v_t̃((t̃)) t̃ s.t. ∫_t̃≥ 0(t̃) t̃≤

    To show f(x) is supermodular, it is sufficient to show that v_t̃ is LS for each time t̃. Toward this end, we can interpret the constraints in (<ref>) in the generalized flow setting as follows. For each machine i, node i has excess capacity 1. For each job j, node j has excess capacity x_j(t̃). Then add an arc from j to i with gain factor 1 / λ_ij for each job j and machine i. Thus the constraints fall in the generalized flow polytope (<ref>). Then we let the cost from j to i be (B λ_ij - w_j t̃/p_ij - 1). From Theorem <ref>, we know v_t̃ is LS which leads to the lemma.


For the sake of completeness, we give the proof of the following lemma that bounds the change of jobs' arrival or completion.


    
    The change of Φ(t) due to the job's completion or arrival is non-positive.


    The proof is almost identical to Lemma <ref> although we use a slightly different potential function.  Thus we only point out the differences when a new job j arrives. Then f (^A   ||  (1/ - 1)^O) increases by at least: 
    
    f(^A ||  p_j _j^A ||  (1/ - 1 )^O  ||  (1/ - 1 ) p_j  _j^O) - f(^A ||  (1/ - 1 ) ^O) 
    
        =  g_(A ∪ j^A ∪ (1/ - 1 ) O ∪ (1/ - 1 ) j^O) -  g_(A ∪ (1/ - 1 ) O)

where = ^A ||  p_j  _j^A ||  (1/ - 1 ) ^O  ||  (1/ - 1 ) p_j  _j^O. By supermodularity of g and using the fact that p^A(r_j) = p^O(r_j) = p_j, we have 

    g_(A ∪ j^A ∪ (1/ - 1 ) O ∪ (1/ - 1 ) j^O ) - g_(A ∪ (1/ - 1 ) O) 
       ≥  g_(A ∪ j^A ∪ (1/ - 1 ) j^O) - g_(A) 
        =g_(A ∪ ( 1/ ) j^A  ) - g_(A)

    Then we can decompose it to a telescopic sum and apply the supermodularity as follows.
    
    = (g_(A ∪ (1 / ) j^A) )- g_(A ∪ (1 /  - 1) j^A ) )+ ... + (g_(A ∪ j^A) - g_(A))  
       ≥1/ ( g_(A ∪ j^A) - g_(A))

    Therefore, Φ(t)'s increase is at most 2/(g_(A ∪ j^A) - g_y(A) - ·1/ ( g_(A ∪ j^A) - g_(A)) ) = 0, as desired. 





  §.§.§ Analysis: Continuous Changes


As before, we let W̃^A(t) = ∑_j w_j/p_j p^A_j(t) be the total remaining fractional weight of our algorithm A at time t. 
Then, let W̃^A_(1)(t) be the fractional weight of jobs processed by the algorithm at t, i.e., W̃^A_(1)(t) := ∑_i,j w_j ∫_t̃ = 0^t̃_iz_ij(t̃)/p_ijt̃ = ∑_i,j w_j ẑ_ij. Let W̃^A_(2)(t) := W̃^A(t) - W̃^A_(1)(t). For brevity, in all of the following lemmas, we omit that we consider a time t when there is no jobs' completion and arrival.
The following lemma shows that the approximate GD still decreases the new residual optimum effectively.


    
    / t f(^A(t)) ≤ -s W̃^A(t).


    Fix any time t and consider the change during time [t, t +  t). Let  be the optimum solution of f(^A(t)), i.e, = min_'_^A(t)('). 
    Recall that our algorithm schedules  during time interval [t, t +  t) and it is given s-speed, i.e., GD processes a job j on machine i by s  t ·ẑ_ij fraction, where ẑ_ij := ∫_t̃=0^t̃_iz_ij(t̃)/p_ijt̃. Now following the same strategy in Lemma <ref>, we need to find a feasible schedule ' (with 1-speed) for remaining job sizes ^A(t) - s  t where Ẑ_j := ∑_i λ_ijẑ_ij. Then, the construction of ' is as follows. First, we remove s  t · z_ij(t̃) / p_ij fraction from  at local time t̃≤t̃_i for job j on machine i. Note that this empties out s  t units of space on the machine because ∑_j ∫_t̃=0^t̃_iz_ij(t̃)/p_ijt̃ = 1. We obtain ' by removing the empty spaces on each machine. 
    
    Let's fix machine i and consider the change of (*) in the residual LP (<ref>). For any t̃ > t̃_i, since s  t ·∑_j ẑ_ij = s  t fraction of jobs completed before time t̃_i, the contribution of z_ij(t̃) in _^A(t +  t)(') becomes at most w_j/p_ij(t̃ - s  t) z_ij(t̃).

    Thus, the decrease of f(^A(t)) from (*) is by at least 
    
    ∑_i,jw_j/p_ij∫_t̃≥t̃_i(t̃ - (t̃ - s  t )) z_ij(t̃) t̃ = s  t  ·∑_i,jw_j/p_ij∫_t̃≥t̃_i z_ij(t̃) t̃ = s t ·W̃^A_(2)(t)

    Since job j gets processed by s  t ·ẑ_ij fraction on machine i, the change of f(^A(t)) from (**) is exactly 
    
    ∑_i,j w_j ( ∫_t̃≥ 0 z_ij(t̃) t̃ - ∫_t̃≥ 0 z'_ij(t̃) t̃)    = ∑_i,j w_j · s  t  ·ẑ_ij = s t ·W̃^A_(1)(t)

    Therefore, the lemma follows by putting two  bounds together.


In the following |_GD and |_ mean that we consider the change due to GD's processing and 's processing alone respectively. 


    
-/ t f (^A(t)  ||  (1/ - 1)^O(t))  |_GD≤ 2s W̃^A(t) + s(1/ - 1) W̃^O(t).



    Fix a time t and consider the change during [t, t +  t), where no job arrives or completes assuming that only GD processes jobs. For notational simplicity, let (t):= ^A(t)  ||  (1/ - 1)^O(t). To achieve our goal of upper bounding the following quantity,
        
    f((t)) - f((t +  t)),

    we construct a feasible solution ” to _(t). Let ' be an optimum solution of f((t +  t)), i.e, ' = min_”'_(t +  t)(”'). Let ” be the time-indexed schedule which first has ẑ_ij for s  t units of time and then exactly follow ' on each machine i. Clearly, we have 
        
    f((t)) - f((t +  t)) ≤_(t) (”) - f((t +  t))

    
    
    Let's first consider the change of (**) in the LP objective. Since GD processes jobs according to the distribution {ẑ_ij}_j during [t, t+ t), (**) decreases by 
    
    ∑_i,j w_j ẑ_ij s  t = W̃^A_(1) s  t,

    as we observed in the proof of Lemma <ref>.
    
    We now turn our attention to the change of (*), which is the fractional weighted completion time of jobs. By scheduling ẑ with speed s, every terms coefficient changes from w_j/ p_ijt̃ to w_j/ p_ij (t̃ - s  t). Thus, the decrease is at most the total fractional weight of all jobs times s  t, which is 
     
    (W̃^A(t) + (1 /  - 1) W̃^O(t)) s  t

    By adding up the upper bounds on the change of (*) and (**) and using the fact that W̃_(1)^A(t) ≤W̃^A(t), we obtain the lemma. 


We now consider the change due to the adversary's processing.
Note that  the RHS consists of W̃^A(t) := ∑_j ∈ A(t) w_jp^A_j(t)/p_j and W^O(t) := ∑_j ∈ O(t) w_j, which denote the  total fractional remaining weight of jobs in A(t) and the total integral weight of jobs in O(t), respectively.


    
    -/ t f (^A(t)  ||  (1/ - 1)^O(t))  |_≤ (1/  - 1) W̃^A(t) + (1/ ) (1/  - 1)  W^O(t).


    The proof of this lemma is very similar to 
    that of Lemma <ref>.
    We keep the same notation for  and '. Since the adversary processing job j with 1 speed is  equivalent to processing all (1 /  - 1) copies of the same job at the same rate, we will pretend that all the copies are distinct jobs and the adversary has (1/  -1)-speed. Clearly, this only gives more power to the adversary. 
    For simplicity we assume that the adversary schedules an integral matching during [t, t +  t), since the extension of the analysis to fractional matching is straightforward. That is, the adversary processes exactly one job j(i) on machine i during [t, t +  t) and processes it on no other machines. Let ẑ^*  denote this schedule. So, z^*_i, j(i) = 1 but z^*_i, j' = 0 for all j' ≠ j(i).    
    Let ” be a schedule that has ẑ^* for (1/  - 1)  t time steps, followed by '.

    We note that (**) decreases by 
    
    ∑_i,j w_j ẑ^*_ij (1 /  -1)  t = ∑_i w_j(i) (1 /  -1)  t ≤ (1 /  -1) W^O(t)   t,

 where the last inequality follows from the fact that j(i) ≠ j(i') for all i ≠ i'. 
    
    By observing that the total fractional weight 
    in ^A(t)  ||  (1/ - 1)^O(t) is W̃^A(t) + (1 /  - 1)W̃^O(t), we can upper bound the change of (*) by 
    
    (1/  - 1)  t (W̃^A(t) + (1 /  - 1)W̃^O(t))

    We obtain the lemma by adding the two upper bounds and using the fact that W̃^O(t) ≤ W^O(t).    

    

    
    Consider any time step t that no arrival or completion of jobs occurs. For < 1/8 and A is given s = 1 + 2-speed, we have / tΦ(t) ≤ - W̃^A(t) + O(1 / ^2) W̃^O(t).


    From Lemma <ref>, Lemma <ref>, and Lemma <ref>, we have 
    
    / tΦ(t)    ≤2/( -s W̃^A(t) + ( (2s + 1/ - 1) W̃^A(t) +  (s + 1/)(1/ - 1) W^O(t) ) ) 
       = 2/( (- + 4^2) W̃^A(t) +  O(1 / ) W^O(t) ))
       ≤ -W̃^A(t) + O(1 / ^2) W^O(t)




By Lemma <ref> and Φ(T) = Φ(0) = 0, we have ∫_t ≥ 0/ tΦ(t) ≥ 0. By Lemma <ref>, we have ∫_t ≥ 0W̃^A(t) ≤ O(1 / ^2) ∫_t ≥ 0 W^O(t). LHS is the total fractional weighted flow time of the algorithm and RHS is the total integral weighted flow time of the optimum schedule. Therefore, by Lemma <ref>, we obtain a (1+)-speed, O(1/^3)-competitive algorithm for the integral objective.






 §.§ Unrelated Machines via Immediate Dispatch

    


In this section, we reproduce the result in <cit.>, which gave a (1+)-speed O(1/ )-competitive algorithm for minimizing total weighted flow time. The analysis of <cit.> was based on dual fitting unlike <cit.>, which gave a (1+)-speed O(1/ ^2)-competitive algorithm using potential functions. We show that potential functions can also achieve an O(1/)-competitive ratio. At the high level, <cit.> considered integral residual optimum unlike <cit.> that used fractional residual optimum.

Since we will use exactly the same algorithm as <cit.> and obtain the same competitive ratio of O(1 /), we will only sketch the analysis, focusing on how our approach leverages supermodularity and gradient descent explicitly.

The algorithm we consider is non-migratory and immediate-dispatch. Let A_i(t) be the jobs assigned to machine i. Note that {A_i(t)}_i will be a partition of A(t). Let ^A_i(t) be the (vector of the) remaining sizes of jobs assigned to  machine i at time t in our algorithm and define ^O_i(t) analogously for the optimum schedule. 

We define f(^A_i(t)) as the residual optimum at time t of the jobs assigned to machine i. Formally,  letting p_ij(t) = p_j(t) / λ_ij, f(^A_i(t)) = ∑_j w_j ∑_j' ≤ j  s.t.  w_j' / p_ij'(t) ≥ w_j /p_ij(t) p_ij'(t) is the minimum total weighted completion time of jobs in A_i(t) pretending that each job j ∈ A_i(t) has a remaining size p_j(t), weight w_j, arrival time 0; ties are broken in an arbitrary but fixed order. Since f is concerned with the single machine scheduling, it is straightforward to show its supermodularity. Then we let f̅(^A(t)) := ∑_i f(^A_i(t)). 

We can restate <cit.> algorithm as follows: When a job j arrives at time t, we permanently assign the job j to the machine i that incurs the minimum increment of the residual optimum f̅(^A(t^-)). Then, we process the jobs on each machine using gradient descent, i.e. follow the residual optimum schedule on the machine. 



For the analysis, we use the following potential function, where f̅(^A(t)  ||  ^O(t)) is defined analogously for jobs in A and O together. 
    
    Φ(t) = 2/(f̅(^A(t)) - 1/2f̅(^A(t)  ||  ^O(t) ))


    While we only consider the non-migratory optimum for brevity, it can be extended to the migratory case, following the approach described in <cit.>.



  
Continuous Changes. If we focus on machine i, we only need to consider the change of 2/( f(^A_i(t)) - 1/2  f(^A_i(t)  ||  ^O_i(t) )). This is exactly the same as the single machine scheduling where we can pretend that we only have jobs in A_i(t) and the adversary has jobs in O_i(t). Thus, 
using Corollary <ref>, we have that 
/ tΦ(t) restricted to machine i is at most - ∑_j ∈ A_i(t) w_j + (1 + 2/) ∑_j ∈ O_i(t) w_j. Summing over all machines we have the following lemma. 

    
    Consider any time t when no job arrives or is completed by our algorithm or the adversary. When GD is given 1+-speed, / tΦ(t) ≤ -W^A(t) + (1 + 2/) W^O(t).




  
Discrete Changes.
The following lemma bounds the potential change due to a job's arrival or completion. Unlike the proofs in the previous section, we take a closer look at the machine to which the job is assigned. 


    
    If Φ(t) changes discontinuously due to a job's arrival or completion, the change is non-positive. 


    For the same reason we used in the proof of Lemma <ref>, we only need to focus on the arrival case. Suppose a new job j arrives at time t. We use the same notations in Lemma <ref>. So j^A and j^O are job j's copy in the schedule of A and O respectively. We assume wlog that job j^A is assigned to machine 1 by the algorithm. If j^O is assigned to the same machine 1, the change of f̅(^A  ||  ^O) is at least
    
    f(^A_1 ||  p_1j_j^A ||  ^O_1 ||  p_1j_j^O) - f(^A_1 ||  ^O_1) ≥ 2 (f(^A_1 ||  p_1j_j^A) - f(^A_1) )

    where the inequality holds due to the supermodularity of f.
    
    Suppose j^O is assigned to another machine, say machine 2. Since the change only occurs on machines 1 and 2, the increase of f̅(^A  ||  ^O) is at least
    
    f(^A_1 ||  p_1j_j^A ||  ^O_1) - f(^A_1 ||  ^O_1) + f(^A_2 ||  ^O_2 ||  p_2j_j^O) - f(^A_2 ||  ^O_2)  
    ≥     f(^A_1 ||  p_1j_j^A) - f(^A_1) + f(^A_2 ||  p_2j_j^O) - f(^A_2) ,

    where the inequality follows from f's supermodularity.
    
    Recall that the algorithm assigns job j to the machine i that gives the minimum increment of f. Thus we have 
    
    f(^A_1 ||  p_1j_j^A) - f(^A_1) ≤ f(^A_2 ||  p_2j_j^O) - f(^A_2)

    Then, Eqn.(<ref>) is at least
       2 (f(_1^A  ||  p_1j_j^A) - f(_1^A) ).
    Thus, in both cases, we have shown that f̅(^A  ||  ^O) increases by at least 2 (f(_1^A  ||  p_1j_j^A) - f(_1^A) ). Since the change of f̅(^A) is exactly
        
    f(^A_1 ||  p_1j_j^A) - f(^A_1),

    we can conclude that  Φ(t)'s change due to job j's arrival is non-positive.         


We combine Lemmas <ref> and 
<ref> as we combined 
Lemma <ref> and  Corollary <ref> at the end of Section <ref>. As a result, we can show that the online algorithm is (1+)-speed O(1/)-competitive  for the total weighted flow time objective. 


§ OTHER RELATED WORK

    

Gross substitutes valuations were introduced by Kelso and Crawford in economics <cit.>. Interestingly, the same valuations were introduced in other areas under different names, such as M^♮-concave functions <cit.>, matroidal maps <cit.>, and valuated matroids <cit.>. Thus, there are several equivalent ways to characterize them. The interested reader is referred to the nice survey  <cit.> and tutorial talk given in ACM EC 2018 <cit.>, and the extensive survey <cit.>. 

We discuss two assumptions we make in this paper, clairvoyance and free preemption. Clairvoyant algorithms are assumed to know a job's size upon its arrival—in contrast, non-clairvoyant algorithms do not until completing the job. See <cit.> for some examples of non-clairvoyant algorithms. There have recently been work to design online algorithms when we are given jobs sizes that are not completely accurate <cit.>, where the  goal is to obtain a schedule almost as good as what the best clairvoyant algorithm can offer when the (predicted) sizes are not far from the actual sizes. In this paper we allow online algorithms to preempt jobs for free. In fact, the flow time minimization becomes computationally very hard without preemption. Thus, non-preemptive scheduling has been studied with resource augmentation even in the offline setting <cit.>. 

In this work we assume there are no precedence constraints among jobs. For online precedence constrained scheduling for total (weighted) flow time, see <cit.>.


There exists a large literature on the “delay" variants of online problems, where the online algorithm can procrastinate its decision incurring delay cost, e.g., <cit.>. The main difference is that in our problem, we have capacitated resources that we can use to process jobs at each time, while the online algorithms pay extra cost for taking an action such as buying a set in their setting. 

Deng <cit.> study Walrasian equilibrium for a market where jobs act as agents bidding for CPU times. Their work considers the single-machine setting, where jobs have different valuations depending on their own completion time. The focus is on the existence and computability of the equilibrium.












§ MISSING PROOFS FOR VALUATION FUNCTIONS

    




 §.§ Proof of Lemma <ref>


    We have  v() = min_≥ 0π() + (See <cit.> Theorem 26, the concavity implies this). Let f(, ) = π() + ·. We can show · is supermodular in  and  when , ≥ 0 using on each coordinate the fact that a b + a' b' ≤max{a, a'}max{b, b'} + min{a, a'}min{b, b'} for any scalars a, a', b, b' ≥ 0.
    Then, we have f(-, ) = π() - ·, which is submodular in  and . By taking the min over all , we know v(-) is submodular for the following reason. 
    Let g(, ) := f(-, ). Let  and ' be such that v(-) = g(, ) and v(-') = g(', '). We then have, 
    
    v(-) + v(-')    = 
            g(, ) + g(', ')  
       ≥ g( ∨', ∨') + g( ∧', ∧')   
       ≥ v( - (∨')) + v( -∧'),

    which proves v(-)'s submodularity  in . 
    So, we have 
    
    v() + v()    = v(- (-)) + v((-)) 
       ≥ v(- (-∨-) + v(-(-∧ -))   
       = v( ∧) + v(∧)









 §.§ Concave Closure of GS: Proof of Theorem <ref>
 

Consider a fixed gross-substitute valuation v:0, 1^n →.[We interchangeably use v(S) and v(_S)] We first observe that for any rational number δ > 0, we can approximate v by a function v':0, 1^n → such that |v(S) - v'(S)| ≤δ for any S ⊆ [n]. This is because due to <cit.> that shows that v is GS if and only if it satisfies a finite number of linear inequalities, we can set up a linear programming with variables {v'(S)}_S ⊆ [n] satisfying the inequalities together with the approximation requirement for all S. The LP has a feasible solution, and particularly a rational number solution since δ∈. Thus, we assume v:0, 1^n → henceforth.


We show that for any ∈^n ∩ [0, 1]^n, we can view v^+() as a convolution of multiples copies of v. The proof is not difficult, but we include it for completeness.


    
    Define ṽ^+ : ^n ∩ [0, 1]^n → such that
    
    ṽ^+() = sup_ = 1 / k! : k ∈_≥ 0max_ /  = _1 + ... + _1 / ∑_i = 1^ 1 /  v(_i)

    where _1, ..., _1 /∈0, 1^n. Then, for any ∈^n ∩ [0, 1]^n, 
    
    ṽ^+() := v^+()
 
    where v^+() = max∑_S v(S) λ_S : ∑_Sλ_S _S = , ∑_Sλ_S = 1, λ_S ≥ 0 is the concave closure of v. 


    Fix a ∈^n ∩ [0, 1]^n. Let λ_S_S be an optimal solution of v^+(); note that λ_S ∈ for all S. Consider an  such that λ_S is an integer multiple of  for all S. To show ṽ^+ () ≥ v^+(), we assign _S to λ_S  / copies of v. Then, 
    ṽ^+ ()  ≥∑_S (λ_S / ) v(_S) = v^+ ().
    Conversely, fix an > 0 such that 1 / is an integer, together with any _1, _2, …, _1 / such that /  = ∑_i=1^1 / _i. Then, by setting λ_S =  |_i = _S_i|, one can immediately show v^+() ≥ṽ^+(). 
    Finally, it is easy to see that ṽ() is well defined as in the definition of ṽ^+(), the quantity monotonically increases as k →∞. 



    Strictly speaking, when we create 1/ copies of v, we also create 1 / copies of each item. Each copy of v is assumed to have no benefit from having more than one copy of any item. It is easy to check that  this valuation function is GS over all the item copies.


The following corollary is immediate from the proof of the above lemma. 

    For any ∈^n ∩ [0, 1]^n, there exists > 0 such that v^+() = ṽ^+() = v^+(), where 
    v^+() =  max_ /  = _1 + ... + _1 / ∑_i = 1^ 1 /  v(_i)





From Lemma <ref>, it is sufficient to show the dual profit of v^+ is submodular. 


    
    The dual profit π^+() = max_∈^n v^+() - · is submodular.


    We first assume ∈^n. When ∈^n, we know = max_' ∈^n v^+(') - ·' is in ^n. Thus, from the previous lemma and corollary, we have v^+() = ṽ^+(). Further, for some > 0, we have v^+() = v^+(). Then, we have,
    
    
    π^+()    = max_∈_+^n v^+() - ·
       = max_∈_+^nmax_ /   = _1 + ... + _1 / ∑_i = 1^ 1 /  v(_i) - ·_i 
       = max__1, ..., _1/∈0, 1^n ∑_i = 1^1 /  v(_i) - ·_i 
       =  ( 1/ ) π() 
       = π()

    
     Thus, we have shown that π^+ coincides with π on all rational vectors . Due to continuity, it does on all real vectors . Since v is a gross-substitute valuation, π is submodular. Therefore, π^+ is submodular, as desired. 




 §.§ Generalized Flow is Linear Substitute


To show that v is LS, from Lemma <ref>, we know that it is equivalent to showing its dual profit π() is submodular w.r.t price vector ∈^n. The following lemma is due to 
Fleischer <cit.> based on LP primal-dual. For a combinatorial proof, see <cit.>.


    
    Let g(S) denote the (cost of the) min-cost flow with non-negative excess at the set of nodes S ⊆ V ∖ V^-, that is the min-cost flow with excess vector b' defined as b'_v = b_v for v ∈ S ∪ V^-; and b'_v = 0 for the other nodes. Then, g is a supermodular.


Intuitively, g measures the cost of the min-cost flow of the underlying network G when we `switch' on a subset S of sources V^-; all the other sources do not generate any flow. As we add more sources, they create more congestion, which causes supermodularity. 

We show that Lemma <ref> implies the valuation function we consider is LS. The proof idea is relatively simple. Due to Lemma <ref>, it suffices to show the dual profit function is submodular. Towards that end, we simulate increasing the price of a job's processing unit by adding/activating new source nodes associated with the job. 


We first show submodularity when the prices are rational numbers, i.e., ∈^n, for any > 0 such that 1 / is an integer, and extend it to arbitrary prices. 



    
    For any ∈ 1 / _+, π^+() = max_∈_+^n v() - · is submodular where ∈_+^n.




     We construct an auxiliary network G̃ such that the min-cost flow of G̃ captures the dual profit -π^ as follows.
    We extend G to  G̃ by adding nodes and arcs as follows. Without declaration, the flow gain γ_e is 1 and the capacity u_e is ∞ for all new arcs e, and the excess b_v are ∞ for all new nodes. Consider the source node for job j in G. Let q_j be its price. First, add a new node j_0 to G and connect it to j by an arc (j_0,j) with cost - c_j. Then we add a series of  arcs: for every j ∈_+, we add a new node j_i, and connect it to j_i-1 with cost . Finally, we set the cost of each arc in G to be 0.

    Then we let g(S) denote the min-cost flow with nonnegative excess at the set of nodes S, that is the excess b' defined as b_v' = b_v for all v ∈ S ∪ V^-; and b_v' = 0 for the other nodes. Now fix any price vector ∈_+^n. Let S_ be a set of nodes that contains j_q_j / , j_q_j /  + 1, ... for each j ∈ J. Then we notice that -π^+() is equal to g(S_). Consider two price vectors , ' ∈_+^n and ≤', and a job j. Note that π^+( + _j) - π^+() = - g(S_ + _j) + g(S_) and S_ + _j + j_q_j /  = S_. Because ≤', we have S_'⊆ S_. Then the lemma follows from the supermodularity of g due to Lemma <ref>. 



    The dual profit π : _+^n → is submodular.



    For any feasible  of v, we can write π() = max_ ( - ) ·. Then, it is clear that π is continuous.
    
    Suppose that π is not submodular. Let , ∈_+^n be the price vectors that violate the submodularity. Then, we have 
    
    
    π() + π() < π(∨) + π(∧)

    
    Let Δ be the difference of the above inequality. 
    From the continuity of π, for some infinitesimally small ' > 0,  we have |π() - π(')|, |π() - π(')|, |π(∨) - π(' ∨')|  and |π(' ∧) - π(' ∧')| are less than ', for some δ such that - '_1 < δ and - '_1 < δ where ',' ∈_+^n for some ∈ 1 / _+. Since Δ - 4 ' > 0, we have 
    
    
    π^+(') + π^+(') < π^+(' ∨') + π^+(' ∧')
  
    
    This would contradict the submodularity of π^+ from Lemma <ref>, and thus we have the lemma. 


§ GRADIENT DESCENT IS NOT A PANACEA

    

In this section, we briefly show that gradient descent is not O(1)-competitive with any O(1)-speed. In the (pull-based) broadcast scheduling <cit.>, the server stores some n pages of useful information. At each time some jobs arrive, each asking for a page. For simplicity, assume all pages are unit-sized. When the server broadcasts a page, it satisfies all jobs requesting the same page and it can broadcast only one page at a time.
Scalable algorithms are known for this problem <cit.>.


Suppose gradient descent has s-speed and s is an integer. Consider the following instance. There are special pages, e_1, e_2, …, e_s. At each time, a total of 2s jobs arrive, two jobs asking for each special page. Further, in every s+1 time steps, one job arrives asking for a distinct page. Suppose the instance ends at time (s+1)T. At each time, gradient descent processes the 2s jobs requesting the special pages, having no time to work on any other jobs. Thus, at time T, it has Ω(T) jobs alive, which have Ω(T) flow time on average. Therefore, gradient descent's total flow time is Ω(T^2). On the other hand, the adversary can repeat the following: Broadcast each of the special s pages and then the unique other page requested. It is easy to see that it satisfies every job within O(1)-time step. Therefore, its total flow time is O(T). 





§ MAKING GRADIENT DESCENT RUN IN POLYNOMIAL TIME

    

The high-level idea is to replace time slots with intervals of exponentially increasing lengths to reduce the number of variables to consider. This idea is commonly used in approximation algorithms to make  a time-indexed LP compact.  While it is straightforward to see it only losing 1+ factor in the approximation ratio, here we should be more careful as we need to show the change of the approximate LP optimum (residual optimum) is 1+-approximate as opposed to what we obtain with the exact residual optimum. 

We define time intervals := { I_h := [a_h, a_h+1)   |   h ≥ 1}, where a_1 < a_2 < … are the integers in [10/ρ^2] ∪{⌊10/ρ^2 (1+ρ)^l ⌋  |   l ≥ 1  }, in increasing order, for some small constant ρ > 0. We will set ρ later and we will assume 1/ ρ is an integer. 
  Let |I| denote the length of the interval I; more precisely, the number of integer time steps in I. 
  The following properties of  are immediate from the construction.


    
The collection  of intervals has the following properties. Let I_H' be the first interval of length greater than 1.

    
  * For all h ≥ 1, |I_h | ≤ |I_h+1|.
    
  * All intervals I_1, I_2, … I_H'-1 have length 1.
    
  * For all h ≥ H', |I_h| ≥1/1+2ρ |I_h+1|.
    




In the residual optimum, we will pretend that time steps in each interval in  are all identical. Towards this end, define g(t) to be a_h where I_h := [a_h, a_h+1) is the unique interval in  including t. So, we will consider the following LP.


    f():= min∑_j ∈ A(t)   w_j/p_j∑_t̃≥ 1 g(t̃) · z_j(t̃) 
    ∑_t̃≥ 1 z_j(t̃) t̃   = x_j   ∀ j ∈ A(t) 
    (t̃)    ∈  ∀t̃≥ 1



Note that in reality, g(t̃) is the same for all t̃∈ I_h, so we can aggregate the variables {z_j(t̃)}_t̃∈ I_h into one; this approximate LP is of compact size. However, we take this full expanded view for the sake of analysis, assuming wlog that z_j(t̃) is the same for all t̃ in each I_h, for any fixed job j.

It is easy to see that replacing t̃ with g(t̃) does not change the residual objective's supermodularity and monotonicity. The only properties we need to check is that the residual objective's change rate remains the same within 1+ factor, under GD and the adversary, which can be easily offset by extra 1+O()-speed augmentation. So, henceforth we aim to show it. 



  
GD remains effective in decreasing the residual optimum.
We first show that processing following the optimum solution to the above LP in the first time step decreases the objective by an amount that is almost equal to the total fractional weight of all jobs. Let := ⟨_1, _2, …, ⟩ be the optimum solution to _. We may use inequalities in the subscript to consider a partial schedule of ; for example, _≥ 2 :=⟨_2, _3, …, ⟩.


    
    Let := ⟨_1, _2, …, ⟩ be the optimum solution to _. Then, 
    f() - f( - _1) ≥_(_≥ 1)  - _ - _1(_≥ 2) ≥1/1+2ρW̃(t).


Before beginning proving the lemma, we first make a simple observation, which will be useful throughout this section. Intuitively, one wants to complete more fractional weights earlier to minimize the objective, which is formally stated below. 


    
    Let V(τ) :=∑_j w_j/p_j z_j(τ). We have V(a_h) ≥ V(a_h+1).
    


    Otherwise, swapping (a_h) and (a_h+1) decreases the LP objective, contradicting 's  optimality.




    The first inequality, f() - f( - _1) ≥_(_≥ 1)  - _ - _1(_≥ 2), follows from the observation that _≥ 2 is a feasible schedule to _ - _1. Let I_H be the last interval where z_j(a_H) has a non-zero value for some j. 
    We then have,

    
    _(_≥ 1)  - _ - _1(_≥ 2) 
    
        =    ∑_j w_j/p_j∑_h ∈ [H] (a_h - a_h-1) z_j(a_h) 
        = ∑_j w_j/p_j∑_h ∈ [H] |I_h-1| z_j(a_h) 
    ≥   ∑_j w_j/p_j∑_h ≤ H' |I_h-1| z_j(a_h) + ∑_j w_j/p_j∑_H' < h  ≤ H |I_h-1| z_j(a_h)     
    ≥   ∑_j  ∑_h ≤ H'w_j/p_j  z_j(a_h) + ∑_j w_j/p_j∑_H' < h  < H1/1+2ρ|I_h| z_j(a_h)   
    
        =    ∑_τ < a_H' V(τ) + 1/|I_H'|∑_a_H'≤τ < a_H'+1 V(τ) + 1/1+2ρ∑_τ≥ a_H'+1 V(τ) 
    ≥   1/1+2ρ∑_τ  V(τ)  
    
        =    1/1+2ρW̃(t)
    
The penultimate inequality follows from Claim  <ref> and |I_H'| ≤ 2ρ a_H'.

By setting ρ small enough (and using slightly more speed augmentation), we will argue that GD effectively decreases the residual optimum. 



  
No need to recompute the residual optimum until a new job arrives.

In the above, we only showed the GD effectively decreases the residual objective for one time step. Here, we further argue that we can just process _1, _2, ...., _t̃ until a new job arrives at time t+ t̃. To this end, we pretend that the residual changes by 

    _ - _≤τ -1(_≥τ)  - _ - _≤τ(_≥τ + 1)

when we process z_τ at time t+τ. 
This is because until a new job arrives at time τ', the residual decreases by at least
_ - _≤ 0(_≥ 1)  - _ - _≤τ'(_≥τ' + 1), and we can decompose it as a telescopic sum, where we pretend that the residual decreases by the amount shown in   Eqn. (<ref>) at each time τ.



  
No algorithm can decrease the residual optimum much more than GD. We need to argue that no algorithm can decrease the residual optimum by more than W̃(t) (with speed 1). To see this, fix an algorithm and suppose it processes _1 in the first time slot, and the optimum schedule for the remaining jobs sizes, - _1, is ⟨_2, _3, …, ⟩. Our goal is to upper bound,


    f() - _ - _1 (_≥ 2)
    ≤   _ - _0 (_≥ 1)  -  _ - _1 (_≥ 2)   
    ≤   ∑_j w_j/p_j∑_h ∈ [H] (a_h - a_h-1) z_j(a_h) 
        = ∑_j w_j/p_j∑_h ∈ [H] |I_h-1| z_j(a_h) 
    ≤   ∑_j w_j/p_j∑_h ∈ [H] |I_h| z_j(a_h) 
       
        
        =    ∑_τ  V(τ) 
        =  W̃(t)
    


    
    No algorithm can decrease the residual optimum by more than W̃(t) at a time t. 




  
Putting the Pieces Together. We use the same potential function we used in the proof of Theorem <ref>, except that f is replaced with the approximate function we consider in Eqn. (<ref>). All the other properties such as supermodularity remain to be satisfied with the approximate residual LP. Thus, the former analysis for discrete events such as jobs arrival or completion continues to hold true (Lemmas <ref>
and <ref>). 
The bound in Lemma <ref> becomes 
/ t f(^A(t)) = - s/1+2ρW̃^A(t) thanks to Lemma <ref>. The bound in Lemma <ref> remains unchanged due to Lemma <ref>. Then, assuming the online algorithm is given (1+)(1+2ρ)-speed, the bound in Corollary <ref> becomes
d/dtΦ(t) ≤ -W̃^A(t) + 
1/((1+)(1+2ρ) + 2) W̃^O(t).
We can set ρ to  to obtain an algorithm that is (1+)(1+2)-speed O(1/ )-competitive for the fractional objective. By scaling  appropriately, we have Theorem <ref>, even with the approximate residual optimum. 
Thus, we have shown polynomial time algorithms achieving the theorem—more precisely, assuming that we have a poly-time separation oracle for whether ∈ or not. As a result, We also have polynomial time algorithms for Theorem <ref> as the proof of the theorem reduces the resource view to the processing rate view.





alpha







