Abstract
We establish a new formalism for problems pertaining to the periodic autocorrelation function of finite sequences, which is suitable for Combinatorial Optimization methods. This allows one to bring to bear powerful Combinatorial Optimization methods in a wide array of problems that can be formulated via the periodic autocorrelation function. Using this new formalism we solve all remaining open problems regarding periodic complementary binary sequences, in the context of the Bömer and Antweiler diagram and thus complete the program that they started in 1990.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bömer L, Antweiler M (1990) Periodic complementary binary sequences. IEEE Trans Inf Theory 36(6):1487–1494
Colbourn CJ, Dinitz JH (eds) (2007) Handbook of combinatorial designs. Discrete mathematics and its applications, 2nd edn. Chapman & Hall/CRC, Boca Raton
Fenimore E, Cannon T (1978) Coded aperture imaging with uniformly redundant arrays. Appl Opt 17:337–347
Floudas CA, Pardalos PM (eds) (2001) Encyclopedia of optimization, vols I–VI. Kluwer Academic, Dordrecht
Glover F, Laguna M (1993) Tabu search. In: Reeves C (ed) Modern heuristic techniques for combinatorial problems. Blackwell, Oxford, pp 70–141
Golomb SW, Gong G (2005) Signal design for good correlation. For wireless communication, cryptography, and radar. Cambridge University Press, Cambridge
Golomb S, Taylor H (1982) Two-dimensional synchronization patterns for minimum ambiguity. IEEE Trans Inf Theory 28:600–604
Hersheya J, Yarlagadda R (1983) Two-dimensional synchronisation. Electron Lett 19:801–803
Kotsireas IS, Koukouvinos C (2008) Periodic complementary binary sequences of length 50. Int J Appl Math 21:509–514
Kotsireas IS, Koukouvinos C (2007) Hadamard ideals and Hadamard matrices from two circulant submatrices. J Comb Math Comb Comput 61:97–110
Koukouvinos C (1996) Sequences with zero autocorrelation. In: Colbourn CJ, Dinitz JH (eds) The CRC handbook of combinatorial designs. CRC Press, Boca Raton. Part IV, Chap 42
Pardalos PM, Prokopyev OA, Shylo OV, Shylo VP (2008) Global equilibrium search applied to the unconstrained binary quadratic optimization problem. Optim Methods Softw 23(1):129–140
Pardalos PM, Rodgers GP (1990) Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45:131–144
Stinson DR (2004) Combinatorial designs. Constructions and analysis. With a foreword by Charles J Colbourn. Springer, New York
Weathers G, Holiday EM (1983) Group-complementary array coding for radar clutter rejection. IEEE Trans Aerosp Electron Syst 19:369–379
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is partially supported by NSF, AirForce and NSERC grants.
Rights and permissions
About this article
Cite this article
Kotsireas, I.S., Koukouvinos, C., Pardalos, P.M. et al. Periodic complementary binary sequences and Combinatorial Optimization algorithms. J Comb Optim 20, 63–75 (2010). https://doi.org/10.1007/s10878-008-9194-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-008-9194-5