Sanjiv Kapoor

Professor, Dept. of Computer Science, Illinois Institute of Technology, Chicago, USA.

e-mail: <last-name>

Current Research Interests:


Selected Publications


Market Equilibrium and Algorithmic Game Theory

A fast and simple algorithm for computing market equilibria

L Fleischer, R Garg, S Kapoor, R Khandekar, A Saberi,

To appear in ACM Transaction on Algorithms, (Conference version in Internet and Network Economics, 19-30, 2008).


Buy-Sell Auction Mechanisms in Market Equilibrium

Sanjiv Kapoor:,WINE 2011: 230-241


An auction-based market equilibrium algorithm for a production model

S Kapoor, A Mehta, V Vazirani

Theoretical Computer Science 378 (2), 153-164, 2007


Market Equilibrium Using Auctions for a Class of Gross-Substitute Utilities.

Rahul Garg, Sanjiv Kapoor:

LNCS, Workshop on Internet and Network Economics, 2007: 356-361


Auction algorithms for market equilibrium

R Garg, S Kapoor, Mathematics of Operations Research(INFORMS) 31 (4), 714-729,  2006 .

(Conference version in ACM STOC 2004).


Price Roll-Back and Path Auctions: A polynomial-time algorithm for the Fisher model.

R. Garg and S. Kapoor, LNCS, Workshop on Internet and Network Economics, 2006.


An auction-based market equilibrium algorithm for the separable gross substitutability case

R Garg, S Kapoor, V Vazirani - Approximation, Randomization, and Combinatorial Optimization, 2004


Nash Equilibrium and the Price of Anarchy in Priority Based Network Routing

Benjamin Grimmer and Sanjiv Kapoor,  INFOCOM 2016.


Price of Anarchy with Heterogeneous Latency Functions

Sanjiv Kapoor, Junghwan Shin, CoRR abs/1407.2991 (2014)


Price of Anarchy in network routing with class based capacity guarantees.

Ehsan Monsef, Tricha Anjali, Sanjiv Kapoor, INFOCOM 2014: 2409-2417


Adversary Games in Secure/Reliable Network Routing.

Gruia Calinescu, Sanjiv Kapoor, Michael Quinn, Junghwan Shin:, GAMENETS 2011: 249-264


Optimization and Network Design

Fast algorithms for convex quadratic programming and multicommodity flows

S Kapoor, PM Vaidya, Proceedings of the eighteenth annual ACM STOC, 1986


Optimum lopsided binary trees

S Kapoor, EM Reingold, Journal of the ACM (JACM) 36 (3), 573-590


Algorithms for generating all spanning trees of undirected, directed and weighted graphs

S Kapoor, H Ramesh, Algorithms and Data Structures, 461-472


Algorithms for enumerating all spanning trees of undirected and weighted graphs

S Kapoor, H Ramesh, SIAM Journal on Computing 24 (2), 247-265


On minimum 3-cuts and approximating k-cuts using cut trees

S Kapoor - Integer Programming and Combinatorial Optimization(IPCO),1996


Speeding up Karmarkar's algorithm for multicommodity flows

S Kapoor, PM Vaidya - Mathematical programming, 1996


Algorithms for Enumerating All Spanning Trees of Directed Graphs,

S. Kapoor and H. Ramesh, Algorithmica 27(2): 120-130 (2000).


Network lifetime and power assignment in ad hoc wireless networks

G Calinescu, S Kapoor, A Olshevsky, A Zelikovsky, Proc.of European Symposium on Algorithms (ESA’03), September 2003, LNCS 2832, pp.114-126.


Bounded Diameter Graph Problems

S. Kapoor and M. Sarwat , Theory of Computing Systems (2007)


Bounded Hops Power Assignment in Ad-hoc Wireless Networks,

G. Calinescu, S. Kapoor, and M. Sarwat, Discrete and Applied Mathematics, Vol 154, Issue 9, June 2006.


Multipath network flows: Bounded buffers and jitter

T Anjali, A Fortin, G Calinescu, S Kapoor, N Kirubanandan, S Tongngam

INFOCOM, 2010 Proceedings IEEE, 1-7


New methodology for transportation investment decisions with consideration of project interdependencies,

Zongzhi Li, Hemanshu Kaul, Sanjiv Kapoor, Eirini Veliou, Bei Zhou, Sang Lee,

Transportation Research Record: Journal of the Transportation Research Board, 2285, pp. 36-46, 2012.

Computational Geometry

Proximity Structures for Geometric Graphs,

Sanjiv Kapoor, Xiang-Yang Li., Int. J. Comput. Geometry Appl. 20(4): 415-429 (2010)


Rectilinear Paths using Corridor Structures,

R. Inkulu and S. Kapoor, CGTA, 2009


Visibility Graph Construction using Corridors,

R.Inkulu and S. Kapoor, CGTA, 2009


Geodesic Spanners on Polyhedral Surfaces, S

anjiv Kapoor, Xiang-Yang Li: ISAAC 2009: 213-223


Dynamically Maintaining Maxima in 2-dimensions,

SIAM J. Comput. 29(6): 1858-1877 (2000)


Efficiently constructing the visibility graph of a Simple Polygon with Obstacles,

S. Kapoor and S.N.Maheshwari), SIAM Journal of Computing. Vol.30, No. 3, 2000, 847-871.


On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees

G Das, S Kapoor, M Smid, Algorithmica 19 (4), 447-462, 1997.


New techniques for exact and approximate dynamic closest-point problems

S Kapoor, M Smid, SIAM Journal on Computing 25 (4), 775-796, 1996.


Lower bounds for maximal and convex layers problems

S Kapoor, P Ramanan, Algorithmica 4 (1-4), 447-459


Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles

S Kapoor, SN Maheshwari, Proceedings of the fourth annual symposium on Computational geometry, 172-182


Rectilinear shortest paths through polygonal obstacles in O (n (log n) 2) time

K Clarkson, S Kapoor, P Vaidya, Proceedings of the third annual symposium on Computational geometry, 251-257





Recent Courses: