Appendix 1 - Definition of Problems

Summary

In this appendix we give the formal definition of the problems that have been used throughout the survey.

CIRCUIT VALUE

Instance: An encoding of a boolean circuit with n gates together with an input assignment.

Solution: The value of the output gate.

LINEAR PROGRAMMING

Instance: An integer m × n matrix A, an integer m-vector b and an integer n-vector c.

Solution: A rational n-vector x such that A x ≤ b.

Measure:c^Tx.

HIGH DEGREE SUBGRAPH

Instance: A graph G = (V, E).

Solution: An induced subgraph H of G.

Measure: The minimum degree of H.

HIGH EDGE CONNECTED SUBGRAPH

Instance: A graph G = (V, E).

Solution: An induced subgraph H of G.

Measure: The edge connectivity of H.

HIGH LINKAGE SUBGRAPH

Instance: A graph G = (V, E).

Solution: An induced subgraph H of G.

Measure: The linkage of H, defined as the maximum minimum degree of any of the subgraphs.

HIGH VERTEX CONNECTED SUBGRAPH

Instance: A graph G = (V, E).

Solution: An induced subgraph H of G.

Measure: The connectivity of H.

LOCAL MAXIMUM CUT

Instance: A graph G = (V, E) together with a partition of V.

Solution: A partition locally optimum for non-oblivious local search.

MAXIMUM ACYCLIC SUBGRAPH

Instance: A digraph G = (V, E).

Solution: Subset E′ ⊆ E such that G′ = (V, A′) is acyclic.

Measure: |E′|.

MAXIMUM 0–1 KNAPSACK

Instance: An integer b and a finite set I = {1,…,n}, for each i ∈ I an integer size S_i and an integer profit p_i

Solution: Subset S ⊆ I such that ∑_i∈Ss_i ≤ b.

Measure: ∑_spi.