Zobrazeno 1 - 10
of 567
pro vyhledávání: '"Garg, Vijay K."'
Autor:
Streit, Robert, Garg, Vijay K.
Matroids provide one of the most elegant structures for algorithm design. This is best identified by the Edmonds-Rado theorem relating the success of the simple greedy algorithm to the anatomy of the optimal basis of a matroid [Edm71; Rad57]. As a re
Externí odkaz:
http://arxiv.org/abs/2408.04118
Autor:
Garg, Vijay K., Streit, Robert P.
We define a new class of predicates called equilevel predicates on a distributive lattice which eases the analysis of parallel algorithms. Many combinatorial problems such as the vertex cover problem, the bipartite matching problem, and the minimum s
Externí odkaz:
http://arxiv.org/abs/2311.06206
Autor:
Garg, Vijay K.
We apply Lattice-Linear Predicate Detection Technique to derive parallel and distributed algorithms for various variants of the stable matching problem. These problems are: (a) the constrained stable marriage problem (b) the super stable marriage pro
Externí odkaz:
http://arxiv.org/abs/2208.01370
Autor:
Hu, Changyong, Garg, Vijay K.
In the Hospitals/Residents problem, every hospital has an upper quota that limits the number of residents assigned to it. While, in some applications, each hospital also has a lower quota for the number of residents it receives. In this setting, a st
Externí odkaz:
http://arxiv.org/abs/2110.15559
Autor:
Hu, Changyong, Garg, Vijay K.
An instance of the super-stable matching problem with incomplete lists and ties is an undirected bipartite graph $G = (A \cup B, E)$, with an adjacency list being a linearly ordered list of ties. Ties are subsets of vertices equally good for a given
Externí odkaz:
http://arxiv.org/abs/2105.09602
Autor:
Garg, Vijay K.
It has been shown that the parallel Lattice Linear Predicate (LLP) algorithm solves many combinatorial optimization problems such as the shortest path problem, the stable marriage problem and the market clearing price problem. In this paper, we give
Externí odkaz:
http://arxiv.org/abs/2103.06264
Autor:
Garg, Vijay K.
Let $L$ be any finite distributive lattice and $B$ be any boolean predicate defined on $L$ such that the set of elements satisfying $B$ is a sublattice of $L$. Consider any subset $M$ of $L$ of size $k$ of elements of $L$ that satisfy $B$. Then, we s
Externí odkaz:
http://arxiv.org/abs/2001.03133
Autor:
Hu, Changyong, Garg, Vijay K.
The popular matching problem is of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a non-empty subset of posts in the order of preference, possibly with ties. A matching M is popular if there is no
Externí odkaz:
http://arxiv.org/abs/1910.13386
Autor:
Garg, Vijay K.
We present a method to design parallel algorithms for constrained combinatorial optimization problems. Our method solves and generalizes many classical combinatorial optimization problems including the stable marriage problem, the shortest path probl
Externí odkaz:
http://arxiv.org/abs/1812.10431