4 papers · 1 filter
Stochastic Network Speed Scaling with Competitive Ratios Independent of the Network
Yash Khanna
In network speed scaling, jobs arrive over time at a network of servers whose speeds can be tuned, every job must be processed by the servers along one of its allowed routes, and t…
Independent Sets in Semi-random Hypergraphs
Yash Khanna, Anand Louis, Rameesh Paul
A set of vertices in a hypergraph is called an independent set if no hyperedge is completely contained inside the set. Given a hypergraph, computing its largest size independent se…
Exact recovery of planted cliques in semi-random graphs
Yash Khanna
In this paper, we study the Planted Clique problem in a semi-random model. Our model is inspired from the Feige-Kilian model [16] which has been studied in many other works [8,11,1…
Planted Models for the Densest -Subgraph Problem
Yash Khanna, Anand Louis
Given an undirected graph , the Densest -subgraph problem (DkS) asks to compute a set of cardinality such that the weight of…