On sizes of complete arcs in PG(2,q)

New upper bounds on the smallest size t(2)(2, q) of a complete arc in the projective plane PG(2, q) are obtained for 853 <= q <= 5107 and q is an element of T-1 boolean OR T-2, where T-1 = (173, 181, 193, 229, 243, 257, 271, 277, 293, 343, 373, 409. 443, 449, 457. 461. 463. 467, 479, 487, 491, 499, 529, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 661. 673. 677, 683. 691, 709}, and T-2 = {5119, 5147, 5153, 5209, 5231, 5237, 5261, 5279, 5281. 5303, 5347, 5641, 5843, 6011, 8192}. From these new bounds it follows that for q <= 2593 and q = 2693. 2753, the relation t(2)(2, q) < 4.5 root q holds. Also, for q <= 5107 we have t(2)(2, q) < 4.74.79 root q. It is shown that for 23 <= q <= 5107 and q is an element of T-2 boolean OR {2(14), 2(15), 2(18)}, the inequality t(2)(2, q) < root q In-0.75 q is true. Moreover, the results obtained allow us to conjecture that this estimate holds for all q >= 23. The new upper bounds are obtained by finding new small complete arcs with the help of a computer search using randomized greedy algorithms. Also new constructions of complete arcs are proposed. These constructions form families of k-arcs in PG(2, q) containing arcs of all sizes k in a region k(min) <= k <= k(max), where k(min) is of order 1/3q or 1/4q while k(max) has order 1/2q. The completeness of the arcs obtained by the new constructions is proved for q <= 2063. There is reason to suppose that the arcs are complete for all q > 2063. New sizes of complete arcs in PG(2, q) are presented for 169 <= q <= 349 and q = 1013, 2003.