linear-time complexity

Convex hulls of superincreasing knapsacks and lexicographic orderings

  • Akshay Gupte
    • Categories Cutting Plane Approaches, Integer Programming Tags , , , ,

    We consider bounded integer knapsacks where the weights and variable upper bounds together form a superincreasing sequence. The elements of this superincreasing knapsack are exactly those vectors that are lexicographically smaller than the greedy solution to optimizing over this knapsack. We describe the convex hull of this n-dimensional set with O(n) facets. We also establish … Read more

    Fast population game dynamics for dominant sets and other quadratic optimization problems

  • Immanuel M. Bomze
  • Marcello Pelillo
  • Samuel Rota-Bulo
    • Categories Data-Mining, Game Theory, Quadratic Programming Tags ,

    We propose a fast population game dynamics, motivated by the analogy with infection and immunization processes within a population of “players,” for finding dominant sets, a powerful graph-theoretical notion of a cluster. Each step of the proposed dynamics is shown to have a linear time/space complexity and we show that, under the assumption of symmetric … Read more