Name

Size

BKS

fbest

fdiff

fpercent

fnum

faverage

σ

t(s)

G1.txt

800

11624

11624

0

100.00%

10

11624

0.00

1.00

G2.txt

800

11620

11620

0

100.00%

10

11620

0.00

3.36

G3.txt

800

11622

11622

0

100.00%

10

11622

0.00

1.95

G4.txt

800

11646

11646

0

100.00%

10

11646

0.00

3.21

G5.txt

800

11631

11631

0

100.00%

10

11631

0.00

1.71

G6.txt

800

2178

2178

0

100.00%

10

2178

0.00

1.43

G7.txt

800

2006

2006

0

100.00%

10

2006

0.00

2.24

G8.txt

800

2005

2005

0

100.00%

10

2005

0.00

2.74

G9.txt

800

2054

2054

0

100.00%

10

2054

0.00

3.34

G10.txt

800

2000

2000

0

100.00%

10

2000

0.00

37.30

G11.txt

800

564

564

0

100.00%

10

564

0.00

18.89

G12.txt

800

556

556

0

100.00%

10

556

0.00

3.71

G13.txt

800

582

582

0

100.00%

10

582

0.00

4.71

G14.txt

800

3064

3064

0

100.00%

2

3063.1

0.57

115.00

G15.txt

800

3050

3050

0

100.00%

9

3049.9

0.32

42.57

G16.txt

800

3052

3052

0

100.00%

10

3052

0.00

67.60

G17.txt

800

3047

3047

0

100.00%

10

3047

0.00

81.57

G18.txt

800

992

992

0

100.00%

10

992

0.00

27.40

G19.txt

800

906

906

0

100.00%

10

906

0.00

5.77

G20.txt

800

941

941

0

100.00%

10

941

0.00

0.96

G21.txt

800

931

931

0

100.00%

10

931

0.00

12.79

G22.txt

2000

13359

13359

0

100.00%

6

13358.6

0.52

86.55

G23.txt

2000

13344

13344

0

100.00%

10

13344

0.00

52.07

G24.txt

2000

13337

13337

0

100.00%

10

13337

0.00

45.86

G25.txt

2000

13340

13340

0

100.00%

9

13339.9

0.32

114.64

G26.txt

2000

13328

13328

0

100.00%

8

13327.6

0.84

73.85

G27.txt

2000

3341

3341

0

100.00%

10

3341

0.00

10.40

G28.txt

2000

3298

3298

0

100.00%

10

3298

0.00

37.13

G29.txt

2000

3405

3405

0

100.00%

10

3405

0.00

40.64

G30.txt

2000

3413

3413

0

100.00%

7

3412.7

0.48

98.53

G31.txt

2000

3310

3310

0

100.00%

8

3309.8

0.42

75.34

G32.txt

2000

1410

1410

0

100.00%

4

1408.8

1.03

116.55

G33.txt

2000

1382

1380

-2

99.86%

7

1379.4

0.97

103.29

G34.txt

2000

1384

1384

0

100.00%

4

1382.8

1.03

62.07

G35.txt

2000

7684

7678

-6

99.92%

1

7674.3

1.89

196.39

G36.txt

2000

7678

7674

-4

99.95%

1

7670.1

2.02

171.59

G37.txt

2000

7689

7686

-3

99.96%

1

7680.2

3.77

157.84

G38.txt

2000

7687

7686

-1

99.99%

1

7680.3

4.16

181.01

G39.txt

2000

2408

2408

0

100.00%

4

2407.1

0.99

125.43

G40.txt

2000

2400

2399

-1

99.96%

1

2398

0.47

98.40

G41.txt

2000

2405

2405

0

100.00%

6

2404.6

0.52

128.79

G42.txt

2000

2481

2480

-1

99.96%

1

2477.4

1.71

182.22

G43.txt

1000

6660

6660

0

100.00%

10

6660

0.00

1.43

G44.txt

1000

6650

6650

0

100.00%

10

6650

0.00

1.21

G45.txt

1000

6654

6654

0

100.00%

10

6654

0.00

5.44

G46.txt

1000

6649

6649

0

100.00%

10

6649

0.00

8.80

G47.txt

1000

6657

6657

0

100.00%

10

6657

0.00

5.92

G48.txt

3000

6000

6000

0

100.00%

10

6000

0.00

1.07

G49.txt

3000

6000

6000

0

100.00%

10

6000

0.00

1.69

G50.txt

3000

5880

5880

0

100.00%

1

5877.4

1.35

63.87

G51.txt

1000

3848

3848

0

100.00%

3

3847.3

0.48

102.52

G52.txt

1000

3851

3851

0

100.00%

5

3850.4

0.70

44.44

G53.txt

1000

3850

3850

0

100.00%

1

3848.3

0.82

158.26

G54.txt

1000

3852

3851

-1

99.97%

9

3850.9

0.32

57.13


On the larger instances the time limit was set to 1200 seconds. Only one run was performed.

 Table 2: MAXCUT G-Set Medium/Large Instance

Name

Size

BKS

fbest

fdiff

fpercent

fnum

t(s)

G55

5000

10299

10296

-3

99.97%

1

1014.87

G56

5000

4017

4013

-4

99.90%

1

663.35

G57

5000

3494

3480

-14

99.60%

1

1007.41

G58

5000

19293

19231

-62

99.68%

1

67.96

G59

5000

6086

6064

-22

99.64%

1

497.37

G60

7000

14188

14178

-10

99.93%

1

958.46

G61

7000

5796

5785

-11

99.81%

1

1039.20

G62

7000

4870

4854

-16

99.67%

1

1144.00

G63

7000

27045

26950

-95

99.65%

1

509.64

G64

7000

8751

8728

-23

99.74%

1

320.19

G65

8000

5562

5530

-32

99.42%

1

972.65

G66

9000

6364

6330

-34

99.46%

1

879.50

G67

10000

6950

6904

-46

99.33%

1

366.81

G70

10000

9591

9579

-12

99.87%

1

1021.41

G72

10000

7008

6962

-46

99.34%

1

854.76

G77

14000

9926

9870

-56

99.43%

1

700.93

G81

20000

14044

13948

-96

99.31%

1

955.83