Computer Science and Engineeringhttps://repository.iitgn.ac.in/handle/123456789/4272019-04-20T17:01:21Z2019-04-20T17:01:21ZImproved linear embeddings via Lagrange dualitySheth, KshiteejGarg, DineshDasgupta, Anirbanhttps://repository.iitgn.ac.in/handle/123456789/43122019-04-12T05:24:07Z2019-03-01T00:00:00ZImproved linear embeddings via Lagrange duality
Sheth, Kshiteej; Garg, Dinesh; Dasgupta, Anirban
Near isometric orthogonal embeddings to lower dimensions are a fundamental tool in data science and machine learning. In this paper, we present the construction of such embeddings that minimizes the maximum distortion for a given set of points. We formulate the problem as a non convex constrained optimization problem. We first construct a primal relaxation and then use the theory of Lagrange duality to create a dual relaxation. We also suggest a polynomial time algorithm based on the theory of convex optimization to solve the dual relaxation provably. We provide a theoretical upper bound on the approximation guarantees for our algorithm, which depends only on the spectral properties of the dataset. We experimentally demonstrate the superiority of our algorithm compared to baselines in terms of the scalability and the ability to achieve lower distortion.
2019-03-01T00:00:00ZBioGen: automated biography generationAmbavi, HeerGarg, AyushNitikshaSharma, MridulSharma, RohitChoudhari, JayeshSingh, Mayankhttps://repository.iitgn.ac.in/handle/123456789/43132019-04-12T05:24:25Z2019-01-02T00:00:00ZBioGen: automated biography generation
Ambavi, Heer; Garg, Ayush; Nitiksha; Sharma, Mridul; Sharma, Rohit; Choudhari, Jayesh; Singh, Mayank
2019-01-02T00:00:00ZOn structural parameterizations of firefightingDas, BireswarEnduri, Murali KrishnaKiyomi, MasashiMisra, NeeldharaOtachi, YotaReddy, I. VinodYoshimura, Shunyahttps://repository.iitgn.ac.in/handle/123456789/42892019-04-12T05:31:45Z2019-03-01T00:00:00ZOn structural parameterizations of firefighting
Das, Bireswar; Enduri, Murali Krishna; Kiyomi, Masashi; Misra, Neeldhara; Otachi, Yota; Reddy, I. Vinod; Yoshimura, Shunya
he Firefighting problem is defined as follows. At time , a fire breaks out at a vertex of a graph. At each time step, a firefighter permanently defends (protects) an unburned vertex, and the fire then spreads to all undefended neighbors from the vertices on fire. This process stops when the fire cannot spread anymore. The goal is to find a sequence of vertices for the firefighter that maximizes the number of saved (non burned) vertices.The Firefighting problem turns out to be-hard even when restricted to bipartite graphs or trees of maximum degree three. We study the parameterized complexity of the Firefighting problem for various structural parameterizations. All our parameters measure the distance to a graph class (in terms of vertex deletion) on which the Firefighting problem admits a polynomial-time algorithm.To begin with, we show that the problem is -hard when parameterized by the size of a modulator to diameter at most two graphs and split graphs. In contrast to the above intractability results, we show that Firefighting is fixed parameter tractable () when parameterized by the size of a modulator to a disjoint union of stars under some complexity-theoretic assumptions.
2019-03-01T00:00:00ZFast and accurate intrinsic symmetry detectionNagar, RajendraRaman, Shanmuganathanhttps://repository.iitgn.ac.in/handle/123456789/42152019-01-16T07:49:19Z2018-12-22T00:00:00ZFast and accurate intrinsic symmetry detection
Nagar, Rajendra; Raman, Shanmuganathan
2018-12-22T00:00:00Z