With No Quest Marker
The marker not appearing is a known bug:
There's a chance that the criminal will have no marker. Sometimes the quest can even move into the completed tab without having finished any of the quest objectives. This makes completing the quest and attempting to receive additional Companion quests impossible even if you happen to find and kill the criminal.
On PC you can get around this through console commands, by accepting and completing one of the other companion radiant quests. The following commands will assign Animal Extermination as a new quest and complete it. Afterwards, you can accept new radiant quests from the companion leaders.
setstage cr01 10
setstage cr01 20
setstage cr01 100
With Quest Marker
If a marker does appear on your map then the best way to find him is not to fast travel to his location since he keeps moving. By the time you get there he will be gone. You should fast travel to a location nearby then continue the rest on foot.
You can find more information (kind of) at the source here.