@article {1539, title = {A Branch-Price-and-Cut Algorithm for Optimal Decoding of LDPC Codes}, journal = {Journal of Global Optimization}, volume = {81}, year = {2021}, pages = {805{\textendash}834}, doi = {https://doi.org/10.1007/s10898-021-01073-4}, author = {Banu Kabakulak and Z C Ta{\c s}k{\i}n and Ali Emre Pusane} } @article {1426, title = {A branch-and-cut algorithm for a bipartite graph construction problem in digital communication systems}, journal = {Networks}, volume = {75}, year = {2020}, pages = {137-157}, abstract = {

Abstract We study a bipartite graph (BG) construction problem that arises in digital communication systems. In a digital communication system, information is sent from one place to another over a noisy communication channel using binary symbols (bits). The original information is encoded by adding redundant bits, which are then used to detect and correct errors that may have been introduced during transmission. Harmful structures, such as small cycles, severely deteriorate the error correction capability of a BG. We introduce an integer programming formulation to generate a BG for a given smallest cycle length. We propose a branch-and-cut algorithm for its solution and investigate the structural properties of the problem to derive valid inequalities and variable fixing rules. We also introduce heuristics to obtain feasible solutions for the problem. The computational experiments show that our algorithm can generate BGs without small cycles in an acceptable amount of time for practically relevant dimensions.

}, keywords = {bipartite graphs, branch-and-cut algorithm, integer programming, symmetry, telecommunications, valid inequalities}, doi = {https://doi.org/10.1002/net.21914}, url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21914}, author = {Banu Kabakulak and Z C Ta{\c s}k{\i}n and Pusane, Ali E.} } @article {1498, title = {The complexity of the defensive domination problem in special graph classes}, journal = {Discrete Mathematics}, volume = {343}, year = {2020}, pages = {111665}, abstract = {

A k-attack on a graph G is a set of k distinct vertices {a1,{\textellipsis},ak} which are said to be under attack. A k-attack A can be countered or defended by a subset of defender vertices X if and only if there exists an injective function f from A to X, such that either f(ai)=ai or (ai,f(ai)) is an edge of G, for all i, 1<=i<=k. Given a graph G, a subset D of V is a k-defensive dominating set of G if and only if D can counter any k-attack in G. We consider the k-defensive dominating set problem. We start a systematic study on the complexity of the k-defensive dominating set problem. When k is not fixed, we show that it is already co-NP-hard to decide whether a given set of vertices is a k-defensive dominating set or not. However, if k is fixed, then we show that the problem is NP-complete even in split graphs. Subsequently, we consider special graph classes, namely paths, cycles, co-chain graphs and threshold graphs. We show that in each of these graph classes, a k-defensive dominating set of minimum size can be found in linear time even for non-fixed k.

}, keywords = {Domination, Networks, Security}, issn = {0012-365X}, doi = {https://doi.org/10.1016/j.disc.2019.111665}, url = {https://www.sciencedirect.com/science/article/pii/S0012365X19303437}, author = {Ekim, Tinaz and Arthur M. Farley and Andrzej Proskurowski} } @article {1428, title = {On the Construction of Regular QC-LDPC Codes With Low Error Floor}, journal = {IEEE Communications Letters}, volume = {24}, year = {2020}, pages = {25-28}, doi = {10.1109/LCOMM.2019.2953058}, author = {Sar{\i}duman, Abdullah and Pusane, Ali E. and Z C Ta{\c s}k{\i}n} } @article {1430, title = {Optimization{\textendash}based decoding algorithms for LDPC convolutional codes in communication systems}, journal = {IISE Transactions}, volume = {51}, year = {2019}, pages = {1061-1074}, abstract = {

AbstractIn a digital communication system, information is sent from one place to another over a noisy communication channel. It may be possible to detect and correct errors that occur during the transmission if one encodes the original information by adding redundant bits. Low{\textendash}Density Parity{\textendash}Check (LDPC) convolutional codes, a member of the LDPC code family, encode the original information to improve error correction capability. In practice these codes are used to decode very long information sequences, where the information arrives in subsequent packets over time, such as video streams. We consider the problem of decoding the received information with minimum error from an optimization point of view and investigate integer programming{\textendash}based exact and heuristic decoding algorithms for its solution. In particular, we consider relax{\textendash}and{\textendash}fix heuristics that decode information in small windows. Computational results indicate that our approaches identify near{\textendash}optimal solutions significantly faster than a commercial solver in high channel error rates. Our proposed algorithms can find higher quality solutions compared with the state of the art iterative decoding heuristic.

}, doi = {10.1080/24725854.2018.1550692}, url = {https://doi.org/10.1080/24725854.2018.1550692}, author = {Banu Kabakulak and Z C Ta{\c s}k{\i}n and Ali Emre Pusane} } @article {671, title = {An Integer Programming-Based Search Technique for Error-Prone Substructures of LDPC Codes}, journal = {AEU - International Journal of Electronics and Communications}, volume = {68}, year = {2014}, pages = {1097-1105}, doi = {10.1016/j.aeue.2014.05.012}, author = {Abdullah Sar{\i}duman and Ali Emre Pusane and Z C Ta{\c s}k{\i}n} } @article {aksen2013bilevel, title = {A bilevel p-median model for the planning and protection of critical facilities}, journal = {Journal of Heuristics}, volume = {19}, number = {2}, year = {2013}, pages = {373{\textendash}398}, publisher = {Springer US}, author = {Aksen, Deniz and Necati Aras and Piyade, Nuray} } @article {aksen2010budget, title = {The budget constrained r-interdiction median problem with capacity expansion}, journal = {Central European Journal of Operations Research}, volume = {18}, number = {3}, year = {2010}, pages = {269{\textendash}291}, publisher = {Springer-Verlag}, author = {Aksen, Deniz and Piyade, Nuray and Necati Aras} } @article {ekim2004approximation, title = {Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa}, journal = {International Journal of Computer Mathematics}, volume = {81}, number = {5}, year = {2004}, pages = {569{\textendash}582}, publisher = {Taylor \& Francis Group}, author = {Ekim, Tinaz and Paschos, Vangelis Th} } @article {bilge2004tabu, title = {A tabu search algorithm for parallel machine total tardiness problem}, journal = {Computers \& Operations Research}, volume = {31}, number = {3}, year = {2004}, pages = {397{\textendash}414}, publisher = {Elsevier}, author = {{\"U}mit Bilge and K{\i}ra{\c c}, Furkan and Kurtulan, M{\"u}jde and Pekg{\"u}n, Pelin} }