Most existing negotiation algorithms only work for bilateral negotiations with linear additive utility functions. Most real-world negotiations however are much more complex. I introduce in this talk a new family of negotiation algorithms that is applicable to domains with many agents, an intractably large space of possible agreements, non-linear utility functions and limited time so an exhaustive search for the best solution is not feasible. This family of algorithms is called NB3 and applies Branch & Bound search to find good plans to propose. Search and negotiation happen simultaneously and therefore strongly influence each other. It applies a new time-based negotiation strategy that considers two utility aspiration levels: one for the agent itself and one for its opponents. Also, we assume a negotiation protocol that imposes almost no restrictions and is therefore also applicable to negotiations with humans. To analyze the performance of the algorithm I will present the Negotiating Salesmen Problem (NSP): a new variant of the Traveling Salesman Problem, in which several salesmen need to negotiate with each other in order to minimize the lengths of their trajectories.