Which are the suitable classification algorithms when the number of categories are more than 1000 Combination of categories is not possible as each class is a distinct brand.
One similar challenge was classifying objects using images (link below) but I could get any specific direction from few papers published regarding the same http://www.image-net.org/challenges/LSVRC/2014/
Alternative approach if algo is not suitable is to build Wordnet/frequency based structure out of available brand-word data & create distance matrix from it Another one is to aggregate the categories & build 2 levels of brand prediction (not sure if it will be effective at all)   
 A: With the limited information that you've given about the dataset, here are few questions that you can consider. I believe you'll need to frame your problem better and purely classification algorithm A Vs. B is not the issue.
Things to Consider


*

*Do you fundamentally believe that the information/independent columns can predict your labels?

*Do you really need the classification to accurately work for all kind of brand labels?


*

*For certain top level brands you can derive the correlation (if product categories are sportswear and sport equipment it is likely to be a Nike). But for certain brands where # of products are small, deriving such correlation may not be possible.


*The problem looks ill posed due to size of dataset (100k rows Vs. 35k labels). A large number of your categories are going to have a single data point where most of the methods are going to fail (for example, it will be hard to do cross-validation on many categories).
Suggestion


*

*Re-frame your problem. Check if you really want to predict 35k possible categories or you are better off considering, let us say, top 100 brands which contribute most of the products.

*For such large scale categorization problems, you can start with neighborhood based models.

*Check the discussion discussion forum of this wikipedia categorization challenge on Kaggle for more ideas. [1]

