np-hard problems

It’s All in the Mix: Wasserstein Classification and Regression with Mixed Features

  • Mohammad Reza Belbasi
  • Aras Selvi
  • Wolfram Wiesemann
    • Categories Optimization in Data Science, Robust Optimization Tags , , ,

    Problem definition: A key challenge in supervised learning is data scarcity, which can cause prediction models to overfit to the training data and perform poorly out of sample. A contemporary approach to combat overfitting is offered by distributionally robust problem formulations that consider all data-generating distributions close to the empirical distribution derived from historical samples, … Read more

    Design and analysis of an approximation algorithm for Stackelberg network pricing

  • Patrice Marcotte
  • Sébastien Roch
  • Gilles Savard
    • Categories Combinatorial Optimization, Network Optimization Tags , , , ,

    We consider the problem of maximizing the revenue raised from tolls set on the arcs of a transportation network, under the constraint that users are assigned to toll-compatible shortest paths. We first prove that this problem is strongly NP-hard. We then provide a polynomial time algorithm with a worst-case precision guarantee of $\frac{1}{2}\log m_T+1$, where … Read more