Apparently the answer is in Appendix B of the same paper, which I had skipped earlier.
The combined algorithm actually maintains two state variables, a cwnd and an ssthresh.
When a time-out occurs due to a packet loss, the variable ssthresh is set to half the current the current window size, cwnd is set to 1, and then slow-start is used to reach that threshold (adding one to the window for every ACK received).
Once the threshold is reached, cwnd is incremented using Additive Increase (one increase for every full window of ACK) received.