First the ^/? at the start is used when you don't know whether you are using Apache 1.x or Apache 2.x (1.x requires a / at the start, 2.x does not). Once you know, adjust your code accordingly.
Second, the ? at the end of ([A-Za-z-]+)? makes no sense at all, unless you really do have a category without a name. Drop that at the end there.
Third, the /? at the end is a bit weird. It's up to you to determine what your URLs are, but now they work both with and without a trailing slash, which may lead to a duplicate content penalty from search engine spiders. I you must allow both with and without it's better to 301 redirect one to the other.
Forth, the / in front of /index.php makes Apache look in the root of the filesystem first to see if the requested file is there. Only when that fails will it look at the root of your web directory. This slows things down unnecessarily, so remove the leading / there.
Lastly, $3 should be $2.
All in all, this would be the end result:
RewriteRule ^cateogry/([A-Za-z-]+)/([0-9-]+)$ index.php?c=$1&start=$2 [L]