What does the cost (C) parameter mean in SVM? I am trying to fit a SVM to my data. My dataset contains 3 classes and I am performing 10 fold cross validation (in LibSVM): 
./svm-train -g 0.5 -c 10 -e 0.1 -v 10 training_data

The help thereby states:
-c cost : set the parameter C of C-SVC, epsilon-SVR, and nu-SVR (default 1)

For me, providing higher cost (C) values gives me higher accuracy. What does C in SVM actually mean? Why and when should I use higher/lower values (or the LibSVM given default value) of C? 
 A: I'm trying to give a simple and easy-to-understand answer. A complete answer would likely need to cover everything from the purpose behind SVMs to the finer details of loss and support vectors. If you want to dig deeper into those details you might need to look into e.g. the chapters about SVMs in the machine learning books out there.
SVMs are large margin classifiers. This means that the (let's assume linear) separation between samples of the black and white class is not just one possible but the best possible separation, defined by obtaining the largest possible margin between samples of the two classes. This would be $H_3$ in the example image:

If you think about this for a moment you will conclude that the separation is derived only from those samples that lie closer to "the other class", hence those close to the margin (to be exact: those on the margin). In the example image, those are the samples marked with the gray lines orthogonal to the $H_3$. This behaviour causes a problem: with the amount of samples used for deriving the separation being largely subset, noise affecting those samples will very likely cause the separation to be suboptimal for the majority of data. This is what we all know as overfitting: the separation would be optimal from the large-margin-point-of-view of the used training, but would generalize badly and therefore be suboptimal for other/yet unseen data.
What we talked about so far is "hard margin classification": we don't allow any samples to be inside the margin, as this is how the margin is defined so far. When we now relax this hard property we end up doing "soft margin classification". The idea behind the margin thereby stays the same - but we can now allow certain samples to be inside the margin. The core benefit is that by doing so, the overall fit of the model to the data might very well be better than with hard margin classification (reduce variance at the cost of some bias). 
So, on the one hand, we still have to solve our plain optimization problem (how to best fit the model = line to our data). On the other hand, we don't want to have all/many samples in the margin - we somehow want to tune how many sample we let inside the margin, so that the margin neither completely overfits, nor completely looses its large margin property. 
An this is where the $C$ parameter enters the stage. The core idea is simple: we modify the optimization problem to optimize both the fit of the line to data and penalizing the amount of samples inside the margin at the same time, where $C$ defines the weight of how much samples inside the margin contribute to the overall error. Consequently, with $C$ you can adjust how hard or soft your large margin classification should be. With a low $C$, samples inside the margins are penalized less than with a higher $C$. With a $C$ of 0, samples inside the margins are not penalized anymore - which is the one possible extreme of disabling the large margin classification. With an infinite $C$ you have the other possible extreme of hard margins. 
Here's a small example visualizing the effect caused by changing $C$ using the well known iris dataset (in R and using the caret package, but the same applies to libsvm too of course). This is how the original data looks like (its a binary classification problem):
library(caret)
d <- iris[51:150,c(1,2,5)]
plot(d[,c(2,1)], pch = ifelse(d[,3]=='versicolor', 1, 2))


This is how changing $C$ can influence the performance of your model:
m <- train(d[,1:2], factor(d[,3]), method = 'svmLinear', trControl = trainControl(method = 'repeatedcv', 10, 20), tuneGrid = expand.grid(C=3**(-7:7)))
plot(m, scales=list(x=list(log=3)))


And this is the difference in separation between two differently chosen $C$ values (note that the separation lines have different inclination!):
m1 <- train(d[,1:2], factor(d[,3]), method = 'svmLinear', preProcess = c('center', 'scale'), trControl = trainControl(method = 'none'), tuneGrid = expand.grid(C=3**(-7)))
plot(m1$finalModel)


m2 <- train(d[,1:2], factor(d[,3]), method = 'svmLinear', preProcess = c('center', 'scale'), trControl = trainControl(method = 'none'), tuneGrid = expand.grid(C=3**(7)))
plot(m2$finalModel)


So, practically, what you most likely want to do in your ML setup is properly tune $C$, e.g. using a tuning grid. You can consider e.g. this publication for more details. Its from the LibSVM guys, and they provide much useful information, from explaining how SVMs work with nice examples to code snippets for how to e.g. use parameter grids with LibSVM:
Hsu et al. (2003). "A practical guide to support vector classification." Department of Computer Science and Information Engineering, National Taiwan University.
BTW: there's a small list of things people said about SVMs $C$ parameter, which I also find helpful for understanding it: http://www.svms.org/parameters/
