function MinimumRunningTime(A)


%==========================================================================
%This code takes as input an aggravated Pater's ERC matrix A corresponding
%to n constraints (encoded as follows: each W is encoded as +1, each L as -1,
%each e as 0). 

%It constructs the corresponding matrix overlineA of update vectors by
%replacing the entry equal to +1 in the ith row for i = 1, ..., n-1 with
%1/w(i) where w(i) is the number of entries equal to +1 in the ith row. 

%It then constructs the matrix D with n-1 rows and n-1 columns. Its generic column
%D_k with k = 1,...,n-1 is defined as the difference between the kth column
%overlineA_k of overlineA and the (k+1)th column overlineA_{k+1} of
%overlineA, multiplied by 6. 

%And it finally returns the solution of the following Linear Program in the 
%indeterminate alpha = (alpha_1, .., alpha_{n-1}):
%       minimize:    alpha^Te 
%       subject to:  D^T alpha >= e
%                    alpha >= 0
%where e is the vector whose entries are all 1 and T stands for transposition.
%==========================================================================



%==========================================================================
%Computes the number m of rows and the number n of columns of the ERC matrix A. 
%For aggravated Pater's matrices, it ought to be m = n-1.
%==========================================================================

s = size(A);
m = s(1);      
n = s(2);        


%==========================================================================
%For every row i = 1,..., m of the ERC matrix A, it computes the number w(i) 
%of entries equal to +1 in the row i (i.e., the number of winner-preferrers)
%==========================================================================

for i = 1 : m
    w(i) = 0;
    for k = 1 : n
        if A(i,k) == 1
            w(i) = w(i) + 1;
        end
    end
end


%==========================================================================
%It constructs the matrix overlineA obtained from the matrix A by replacing
%each entry equal to +1 with 1/w(i), where w(i) is the number of +1's in the
%ith row where that entry belongs, as computed above
%==========================================================================

overlineA = A;
for i = 1: m
    for k = 1 : n
        if overlineA(i,k) == 1
            overlineA(i,k) = 1/w(i);
        end
    end
end


%==========================================================================
%It constructs the matrix D with n-1 rows and n-1 columns whose generic column
%D_k with k = 1,...,n-1 is defined as the difference between the kth column
%overlineA_k of overlineA and the (k+1)th column overlineA_{k+1} of
%overlineA multiplied by 6.
%==========================================================================

for k = 1 : n-1
    D(:,k) = 6 * overlineA(:,k) - overlineA(:, k+1);
end


%==========================================================================
%It solves the following Linear Program in the indeterminate 
%alpha = (alpha_1, .., alpha_{n-1}) using a Matlab built-in subroutine:
%       minimize:   alpha^Te 
%       subject to: D^T alpha >= e
%                   alpha >= 0
where e is the vector whose entries are all 1 and T stands for transposition
%==========================================================================

f = ones(m,1);
Matrix = -D';
b = - ones(n-1,1) ;
lb = zeros(m,1);
[alpha, MinimumRunningTime ] = linprog(f, Matrix, b, [], [], lb)



