Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 8, 2026

Available Issues

April 10, 2013 - May 8, 2026

Semidefinite Approximations for Bicliques and Bi-Independent Pairs

Published Online:13 Mar 2024https://doi.org/10.1287/moor.2023.0046

References

  • [1] Alon N, Duke RA, Lefmann H, Rödl V, Yuster R (1994) The algorithmic aspects of the regularity lemma. J. Algorithms 16:80–109.Crossref, Google Scholar
  • [2] Al-Yamani AA, Ramsundar S, Pradhan DK (2007) A defect tolerance scheme for nanotechnology circuits. IEEE Trans. Circuits Systems I. Regular Papers 54(11):2402–2409.Crossref, Google Scholar
  • [3] Brouwer AE, Haemers WH (2017) Spectra of Graphs (Springer, New York).Google Scholar
  • [4] Chen J, Kanj IA (2003) Constrained minimum vertex cover in bipartite graphs: Complexity and parametrized algorithms. J. Comput. System Sci. 67:833–847.Crossref, Google Scholar
  • [5] Chen L, Liu C, Zhou R, Xu J, Li J (2021) Efficient exact algorithms for maximum balanced biclique search in bipartite graphs. SIGMOD ‘21: Proc. 2021 Internat. Conf. Management Data, vol. 21 (ACM Press, New York), 20–25.Google Scholar
  • [6] Cvetković D, Simić S (1995) The second-largest eigenvalue of a graph (a survey). Filomat (Niś) 9(3):449–472.Google Scholar
  • [7] Dawande M, Keskinocak P, Tayur S (1997) On the biclique problem in bipartite graphs. Technical report, Carnegie-Mellon University, Pittsburgh.Google Scholar
  • [8] Dawande M, Keskinocak P, Swaminathan JM, Tayur S (2001) On bipartite and multipartite clique problems. J. Algorithms 41:388–403.Crossref, Google Scholar
  • [9] Delorme C, Poljak S (1993) Combinatorial properties and the complexity of a max-cut approximation. Eur. J. Combin. 14(4):313–333.Crossref, Google Scholar
  • [10] Eğecioğlu Ö, King A (1999) Random walks and Catalan factorization. Congressus Numerantium 138:129–140.Google Scholar
  • [11] Erdös P, Ko C, Rado R (1961) Intersecting theorems for systems of finite sets. Quart. J. Math. 12(2):313–320.Crossref, Google Scholar
  • [12] Feller W (1957) An Introduction to Probability Theory and Its Applications, 3rd ed. (Wiley, New York).Google Scholar
  • [13] Fiorini S, Kaibel V, Pashkovich K, Theis DO (2013) Combinatorial bounds on nonnegative rank and extended formulations. Discrete Math. 313:67–83.Crossref, Google Scholar
  • [14] Fiorini S, Massar S, Pokutta S, Tiwary HR, de Wolf R (2012) Linear vs. semidefinite extended formulations: Exponential separation and strong lower bounds. STOC 2012: Proc. 44th Annual ACM Sympos. Theory Comput. (ACM Press, New York), 95–106.Google Scholar
  • [15] Folkman J (1967) Regular line-symmetric graphs. J. Combin. Theory 3(3): 215–232.Crossref, Google Scholar
  • [16] Garey MR, Johnson DS (1979) Computers and Intractability. A Guide to the Theory of NP-Completeness (Freeman, San Francisco).Google Scholar
  • [17] Gijswijt DC, Mittelmann HD, Schrijver A (2012) Semidefinite code bounds based on quadruple distances. IEEE Trans. Inform. Theory 58:2697–2705.Crossref, Google Scholar
  • [18] Gowers WT (2008) Quasirandom groups. Combin. Probab. Comput. 17:363–387.Crossref, Google Scholar
  • [19] Grötschel M, Lovász L, Schrijver A (1988) Geometric Algorithms and Combinatorial Optimization (Springer-Verlag, Berlin).Crossref, Google Scholar
  • [20] Gurobi Optimization LLC (2023) Gurobi Optimizer reference manual. http://www.gurobi.com.Google Scholar
  • [21] Haemers WH (1997) Disconnected vertex sets and equidistant code pairs. Electronic J. Combin. 4(1):R7.Crossref, Google Scholar
  • [22] Haemers WH (2001) Bicliques and eigenvalues. J. Combin. Theory Ser. B 82:56–66.Crossref, Google Scholar
  • [23] Haemers WH (2021) Hoffman’s ratio bound. Linear Algebra Appl. 617:215–219.Crossref, Google Scholar
  • [24] Johnson DS (1987) The NP-Completeness column: An ongoing guide. J. Algorithms 8:438–448.Crossref, Google Scholar
  • [25] Josz C, Henrion D (2016) Strong duality in Lasserre’s hierarchy for polynomial optimization. Optim. Lett. 10:3–10.Crossref, Google Scholar
  • [26] Karp R (1972) Reducibility Among Combinatorial Problems. Complexity of Computer Computations (Plenum Press, New York), 85–103.Crossref, Google Scholar
  • [27] Kedlaya KS (2009) Product-free subsets of groups, then and now. Contemporary Math. 479:169–177.Crossref, Google Scholar
  • [28] Keevash P, Lifshitz N, Minzer D (2022) On the largest product-free subsets of the alternating groups. Preprint, submitted May 30, https://arxiv.org/abs/2205.15191.Google Scholar
  • [29] Krivelevich M, Sudakov B (2003) Sparse pseudo-random graphs are Hamiltonian. J. Graph Theory 42:17–33.Crossref, Google Scholar
  • [30] Lasserre J-B (2001) An explicit exact SDP relaxation for nonlinear 0-1 programs. Aardal K, Gerards AMH, eds. Integer Programming and Combinatorial Optimization. IPCO 2001. Lecture Notes in Computer Science, vol. 2081 (Springer, Berlin, Heidelberg), 293–303.Crossref, Google Scholar
  • [31] Laurent M (2003) A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0-1 programming. Math. Oper. Res. 28(3):470–496.Link, Google Scholar
  • [32] Litjens BM, Polak S, Schrijver A (2017) Semidefinite bounds for nonbinary codes based on quadruples. Designs Codes Cryptography 84:87–100.Crossref, Google Scholar
  • [33] Lovász L (1979) On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25:1–7.Crossref, Google Scholar
  • [34] Mohar B (1989) Isoperimetric numbers of graphs. J. Combin. Theory Ser. B 47:274–291.Crossref, Google Scholar
  • [35] Mukhopadhyay A, Ray S, Maulik U (2014) Incorporating the type and direction information in predicting novel regulatory interactions between HIV-1 and human proteins using a biclustering approach. BMC Bioinformatics 15(1):26.Crossref, Google Scholar
  • [36] Nilli A (1991) On the second eigenvalue of a graph. Discrete Math. 91:207–210.Crossref, Google Scholar
  • [37] OEIS Foundation Inc. (2022) The on-line encyclopedia of integer sequences, entry A307768. Accessed December 1, 2022, http://oeis.org/A307768.Google Scholar
  • [38] Peeters R (2003) The maximum edge biclique problem is NP-hard. Discrete Appl. Math. 131:651–654.Crossref, Google Scholar
  • [39] Pyber L (1986) A new generalization of the Erdös-Ko-Rado theorem. J. Combin. Theory Ser. A 43:85–90.Crossref, Google Scholar
  • [40] Ravi SS, Lloyd EL (1988) The complexity of near-optimal programmable logic array folding. SIAM J. Comput. 17(4):696–710.Crossref, Google Scholar
  • [41] Suda S, Tanaka H (2014) A cross-intersection theorem for vector spaces based on semidefinite programming. Bull. London Math. Soc. 46:342–348.Crossref, Google Scholar
  • [42] Suda S, Tanaka H, Tokushige N (2017) A semidefinite programming approach to a cross-intersection problem with measures. Math. Programming Ser. A 166:113–130.Crossref, Google Scholar
  • [43] Swaminathan JM, Tayur S (1998) Management of broader product lines through delayed product differentiation using vanilla boxes. Management Sci. 44:161–172.Link, Google Scholar
  • [44] Tahoori MB (2006) Application-indepenedent defect tolerance of reconfigurable nanoarchitectures. ACM J. Emerging Tech. Comput. Systems 2(3):197–218.Crossref, Google Scholar
  • [45] Vallentin F (2020) Semidefinite programming bounds for product free subsets in groups. Presentation, November 2, Polynomial Optimization, Efficiency through Moments and Algebra, http://poema-network.eu/meeting/workshop-2-november-2020.Google Scholar
  • [46] Vavasis S (2009) On the complexity of nonnegative matrix factorization. SIAM J. Optim. 20:1364–1377.Crossref, Google Scholar
  • [47] Yang H, Wang H, Wang W, Yu PS (2005) An improved biclustering method for analyzing gene expression profiles. Internat. J. Artificial Intelligence Tools 14(5):771–789.Crossref, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree