2 citations · 6 across the 15 of their papers we have counts for
4 papers · 1 filter
An Improved Integrality Gap for Steiner Tree
Ali Çivril, Muhammed Mirza Biçer, Berkay Tahsin Tunca +1
A promising approach for obtaining improved approximation algorithms for Steiner tree is to use the bidirected cut relaxation (BCR). The integrality gap of this relaxation is at le…
Sparse Approximation is Provably Hard under Coherent Dictionaries
Ali Çivril
It is well known that sparse approximation problem is \textsf{NP}-hard under general dictionaries. Several algorithms have been devised and analyzed in the past decade under variou…
Sparse Approximation by Semidefinite Programming
Ali Çivril
The problem of sparse approximation and the closely related compressed sensing have received tremendous attention in the past decade. Primarily studied from the viewpoint of applie…
Improved Inapproximability Results for Steiner Tree via Long Code Based Reductions
Ali Çivril
The best algorithm for approximating Steiner tree has performance ratio [J. Byrka et al., \textit{Proceedings of the 42th Annual ACM Symposium on Theory of…