7 citations · 29 across the 31 of their papers we have counts for
6 papers · 1 filter
Scarf's Algorithm on Arborescence Hypergraphs
Karthekeyan Chandrasekaran, Yuri Faenza, Chengyue He +1
Scarf's algorithm--a pivoting procedure that finds a dominating extreme point in a down-monotone polytope--can be used to show the existence of a fractional stable matching in hype…
The Maximum Binary Tree Problem
Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate +3
We introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree…
Invertibility and Largest Eigenvalue of Symmetric Matrix Signings
Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang +1
The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of ident…
Additive Stabilizers for Unstable Graphs
Karthekeyan Chandrasekaran, Corinna Gottschalk, Jochen Könemann +3
Stabilization of graphs has received substantial attention in recent years due to its connection to game theory. Stable graphs are exactly the graphs inducing a matching game with…
Deciding Orthogonality in Construction-A Lattices
Karthekeyan Chandrasekaran, Venkata Gandikota, Elena Grigorescu
Lattices are discrete mathematical objects with widespread applications to integer programs as well as modern cryptography. A fundamental problem in both domains is the Closest Vec…
Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections
Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler
We determine the thresholds for the number of variables, number of clauses, number of clause intersection pairs and the maximum clause degree of a k-CNF formula that guarantees sat…