MediumCalculusca-228

Kantorovich Potential Step

Problem

The c-transform of a Kantorovich potential g is f_i = min_j (C_ij - g_j), which is one step of the alternating dual ascent for optimal transport.

Given the cost matrix C and the current potential g, return the transformed potential f.

Hint

Alternating c-transforms converge to the optimal dual potentials.

case 1

in: [[[0,2],[3,0]],[0,0]]

expected: [0,0]

case 2

in: [[[1,2],[3,4]],[0.5,0]]

expected: [0.5,2.5]

case 3

in: [[[5]],[1]]

expected: [4]

case 4

in: [[[1,2],[3,0]],[2,1]]

expected: [-1,-1]

Starter codePython

def kantorovich_ctransform(cost, g):
    # Your code here
    pass

4 test cases · run your code against them in the editor