American Institute of Mathematical Sciences

Advanced
August  2010, 4(3): 419-431. doi: 10.3934/amc.2010.4.419

Combinatorial batch codes and transversal matroids

Richard A. Brualdi 1, , Kathleen P. Kiernan 1, , Seth A. Meyer 1, and  Michael W. Schroeder 1,

1. 

Department of Mathematics, University of Wisconsin, Madison, WI 53706, United States, United States, United States, United States

Received  January 2010 Revised  May 2010 Published  August 2010

Combinatorial batch codes were defined by Paterson, Stinson, and Wei as purely combinatorial versions of the batch codes introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai. There are $n$ items and $m$ servers each of which stores a subset of the items. It is required that, for prescribed integers $k$ and $t$, any $k$ items can be retrieved by reading at most $t$ items from each server. Only the case $t=1$ is considered here. An optimal combinatorial batch code is one in which the total storage required is a minimum. We establish an important connection between combinatorial batch codes and transversal matroids, and exploit this connection to characterize optimal combinatorial batch codes if $n=m+1$ and $n=m+2$.
Keywords: presentation of a transversal matroid., transversal matroid, Combinatorial batch codes, cocircuit, dual matroid.
Mathematics Subject Classification: Primary: 05B30, 05B35, 05D05, 68P20, 68R0.
Citation: Richard A. Brualdi, Kathleen P. Kiernan, Seth A. Meyer, Michael W. Schroeder. Combinatorial batch codes and transversal matroids. Advances in Mathematics of Communications, 2010, 4 (3) : 419-431. doi: 10.3934/amc.2010.4.419
[1]

M. B. Paterson, D. R. Stinson, R. Wei. Combinatorial batch codes. Advances in Mathematics of Communications, 2009, 3 (1) : 13-27. doi: 10.3934/amc.2009.3.13
[2]

JiYoon Jung, Carl Mummert, Elizabeth Niese, Michael Schroeder. On erasure combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (1) : 49-65. doi: 10.3934/amc.2018003
[3]

Srimanta Bhattacharya, Sushmita Ruj, Bimal Roy. Combinatorial batch codes: A lower bound and optimal constructions. Advances in Mathematics of Communications, 2012, 6 (2) : 165-174. doi: 10.3934/amc.2012.6.165
[4]

Yuebo Shen, Dongdong Jia, Gengsheng Zhang. The results on optimal values of some combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (4) : 681-690. doi: 10.3934/amc.2018040
[5]

Eugen Mihailescu, Mariusz Urbański. Transversal families of hyperbolic skew-products. Discrete & Continuous Dynamical Systems - A, 2008, 21 (3) : 907-928. doi: 10.3934/dcds.2008.21.907
[6]

Carlos Gutierrez, Víctor Guíñez, Alvaro Castañeda. Quartic differential forms and transversal nets with singularities. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 225-249. doi: 10.3934/dcds.2010.26.225
[7]

Stefka Bouyuklieva, Zlatko Varbanov. Some connections between self-dual codes, combinatorial designs and secret sharing schemes. Advances in Mathematics of Communications, 2011, 5 (2) : 191-198. doi: 10.3934/amc.2011.5.191
[8]

Chen-Chang Peng, Kuan-Ju Chen. Existence of transversal homoclinic orbits in higher dimensional discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2010, 14 (3) : 1181-1197. doi: 10.3934/dcdsb.2010.14.1181
[9]

B. Campos, P. Vindel. Transversal intersections of invariant manifolds of NMS flows on $S^{3}$. Discrete & Continuous Dynamical Systems - A, 2012, 32 (1) : 41-56. doi: 10.3934/dcds.2012.32.41
[10]

Flaviano Battelli, Ken Palmer. Transversal periodic-to-periodic homoclinic orbits in singularly perturbed systems. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 367-387. doi: 10.3934/dcdsb.2010.14.367
[11]

Yurong Li, Zhengdong Du. Applying battelli-fečkan's method to transversal heteroclinic bifurcation in piecewise smooth systems. Discrete & Continuous Dynamical Systems - B, 2019, 24 (11) : 6025-6052. doi: 10.3934/dcdsb.2019119
[12]

Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039
[13]

Cuiling Fan, Koji Momihara. Unified combinatorial constructions of optimal optical orthogonal codes. Advances in Mathematics of Communications, 2014, 8 (1) : 53-66. doi: 10.3934/amc.2014.8.53
[14]

Cem Güneri, Ferruh Özbudak, Funda ÖzdemIr. On complementary dual additive cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 353-357. doi: 10.3934/amc.2017028
[15]

Gabriele Nebe, Wolfgang Willems. On self-dual MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 633-642. doi: 10.3934/amc.2016031
[16]

Sergio R. López-Permouth, Benigno R. Parra-Avila, Steve Szabo. Dual generalizations of the concept of cyclicity of codes. Advances in Mathematics of Communications, 2009, 3 (3) : 227-234. doi: 10.3934/amc.2009.3.227
[17]

Csilla Bujtás, Zsolt Tuza. Optimal batch codes: Many items or low retrieval requirement. Advances in Mathematics of Communications, 2011, 5 (3) : 529-541. doi: 10.3934/amc.2011.5.529
[18]

Masaaki Harada, Akihiro Munemasa. Classification of self-dual codes of length 36. Advances in Mathematics of Communications, 2012, 6 (2) : 229-235. doi: 10.3934/amc.2012.6.229
[19]

Stefka Bouyuklieva, Anton Malevich, Wolfgang Willems. On the performance of binary extremal self-dual codes. Advances in Mathematics of Communications, 2011, 5 (2) : 267-274. doi: 10.3934/amc.2011.5.267
[20]

Nikolay Yankov, Damyan Anev, Müberra Gürel. Self-dual codes with an automorphism of order 13. Advances in Mathematics of Communications, 2017, 11 (3) : 635-645. doi: 10.3934/amc.2017047

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (15)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences