Search results for: COST COLORING

• Linear game non-contextuality and Bell inequalities—a graph-theoretic approach

  Publication

  • M. Rosicka
  • R. Ramanathan
  • P. Gnaciński
  • K. Horodecki
  • M. Horodecki
  • P. Horodecki
  • S. Severini

  - NEW JOURNAL OF PHYSICS - Year 2016

  We study the classical and quantum values of a class of one-and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR(XOR-d) games we study are a subclass of the well-known linear games. We introduce a 'constraint graph' associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the...

  Full text available to download

• Approximation algorithms for job scheduling with block-type conflict graphs

  Publication

  • H. Furmańczyk
  • T. Pikies
  • I. Sokołowska
  • K. Turowski

  - COMPUTERS & OPERATIONS RESEARCH - Year 2024

  The problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality criterion, is considered in this paper. No two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine in this model. The presented model stems from a well-established line of research combining scheduling theory...

  Full text to download in external service