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]

Xin Sun, Dachuan Xu, Dongmei Zhang, Yang Zhou. An adaptive algorithm for maximization of non-submodular function with a matroid constraint. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022031
[2]

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
[3]

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
[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]

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
[6]

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

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

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
[9]

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

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

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

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

Mourad Bellassoued, Zouhour Rezig. Recovery of transversal metric tensor in the Schrödinger equation from the Dirichlet-to-Neumann map. Discrete and Continuous Dynamical Systems - S, 2022, 15 (5) : 1061-1084. doi: 10.3934/dcdss.2021158
[14]

Jorge Morales Paredes, Félix Humberto Soriano Méndez. On the Cauchy problems associated to a ZK-KP-type family equations with a transversal fractional dispersion. Discrete and Continuous Dynamical Systems, 2022, 42 (5) : 2257-5593. doi: 10.3934/dcds.2021190
[15]

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
[16]

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
[17]

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
[18]

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

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
[20]

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

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (102)
  • HTML views (0)
  • Cited by (23)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy