Ivan Bliznets

Ivan Bliznets

Auto-generated profile, based on publicly available information

Ivan Bliznets

University of Groningen

Research Focus & Metrics

Academic Career Length

15Years (2012-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
22 August 2016
Verified
Conference Paper
Open access
PDF file
VJVirajith Jalaparti
Virajith Jalaparti
IBIvan Bliznets
Ivan Bliznets
SKSrikanth Kandula
Srikanth Kandula
BLBrendan Lucier
Brendan Lucier
IMIshai Menache
Ishai Menache
Neither traffic engineering nor fixed prices (e.g., \\$/GB) alone fully address the challenges of highly utilized inter-datacenter WANs. The former offers more service to users who overstate their demands and poor service overall. The latter offers no service guarantees to customers, and providers have no lever to steer customer demand to lightly loaded paths/times. To address these issues, we design and evaluate Pretium -- a framework that combines dynamic pricing with traffic engineering for inter-datacenter bandwidth. In Pretium, users specify their required rates or transfer sizes with deadlines, and a price module generates a price quote for different guarantees (promises) on these requests. The price quote is generated using internal prices (which can vary over time and links) which are maintained and periodically updated by Pretium based on history. A supplementary schedule adjustment module gears the agreed-upon network transfers towards an efficient operating point by optimizing time-varying operation costs. Experiments using traces from a large production WAN show that Pretium improves total system efficiency (value of routed transfers minus operation costs) by more than 3.5X relative to current usage-based pricing schemes, while increasing the provider profits by 2X.

1 January 2015 in SIAM Journal on Discrete Mathematics
Verified
Journal Article
Closed access
IBIvan Bliznets
Ivan Bliznets
FFFedor V. Fomin
Fedor V. Fomin
MPMarcin Pilipczuk
Marcin Pilipczuk
MPMichał Pilipczuk
Michał Pilipczuk
In the Proper Interval Completion problem we are given a graph $G$ and an integer $k$, and the task is to turn $G$ using at most $k$ edge additions into a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of Proper Interval Completion from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir, and Tarjan [SIAM J. Comput., 28 (1999), pp. 1906--1922], who showed an algorithm for the problem working in $\mathcal{O}(16^k\cdot (n+m))$ time. In this paper we present an algorithm with running time $k^{\mathcal{O}(k^{2/3})} + \mathcal{O}(nm(kn+m))$, which is the first subexponential parameterized algorithm for Proper Interval Completion.

6 May 2018 in ACM Transactions on Computation Theory
Verified
Journal Article
Open access
IBIvan Bliznets
Ivan Bliznets
MCMarek Cygan
Marek Cygan
PKPaweł Komosa
Paweł Komosa
MPMichał Pilipczuk
Michał Pilipczuk
The H - free E dge D eletion problem asks, for a given graph G and integer k , whether it is possible to delete at most k edges from G to make it H -free—that is, not containing H as an induced subgraph. The H - free E dge C ompletion problem is defined similarly, but we add edges instead of deleting them. The study of these two problem families has recently been the subject of intensive studies from the point of view of parameterized complexity and kernelization. In particular, it was shown that the problems do not admit polynomial kernels (under plausible complexity assumptions) for almost all graphs H , with several important exceptions occurring when the class of H -free graphs exhibits some structural properties. In this work, we complement the parameterized study of edge modification problems to H -free graphs by considering their approximability. We prove that whenever H is 3-connected and has at least two nonedges, then both H - free E dge D eletion and H - free E dge C ompletion are very hard to approximate: they do not admit poly(OPT)-approximation in polynomial time, unless P=NP, or even in time subexponential in OPT, unless the exponential time hypothesis fails. The assumption of the existence of two nonedges appears to be important: we show that whenever H is a complete graph without one edge, then H - free E dge D eletion is tightly connected to the M in H orn D eletion problem, whose approximability is still open. Finally, in an attempt to extend our hardness results beyond 3-connected graphs, we consider the cases of H being a path or a cycle, and we achieve an almost complete dichotomy there.

15 December 2012 in Journal of Mathematical Sciences
Verified
Journal Article
Closed access
PDF file
IBI. A. Bliznets
I. A. Bliznets

22 August 2015 in Algorithmica
Verified
Journal Article
Open access
PDF file
IBIvan Bliznets
Ivan Bliznets
FFFedor V. Fomin
Fedor V. Fomin
MPMichał Pilipczuk
Michał Pilipczuk
YVYngve Villanger
Yngve Villanger
We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time \(\mathcal {O}(2^{\lambda n})\) for some \(\lambda <1\). These are the first algorithms breaking the trivial \(2^n n^{\mathcal {O}(1)}\) bound of the brute-force search for these problems.

1 January 2014 in Lecture Notes in Computer Science
Verified
Book Chapter
Closed access
PDF file
IBIvan Bliznets
Ivan Bliznets
FFFedor V. Fomin
Fedor V. Fomin
MPMarcin Pilipczuk
Marcin Pilipczuk
MPMichał Pilipczuk
Michał Pilipczuk