Digital Elevation Model Accuracy Aspects (2008)
Mandla V. Ravibabu, Kamal Jain
Within the context of Geographical Information Systems (GIS), several types of surface models are being used in a spatial modeling environment. DEM is a fundamental requirement for many GIS...
Garg, Dinesh, Jain, Kamal, Talwar, Kunal, Vazirani, Vijay V
We provide the first strongly polynomial time exact combinatorial algorithm to compute Fisher equilibrium for the case when utility functions do not satisfy the Gross substitutability property. The...
Garg, Dinesh, Jain, Kamal, Talwar, Kunal, Vazirani, Vijay V
We provide the first strongly polynomial time exact combinatorial algorithm to compute Fisher equilibrium for the case when utility functions do not satisfy the Gross substitutability property. The...
Site Suitability Analysis for Urban Development Using GIS (2007)
Kamal Jain, Y. Venkata Subbaiah
The future success of economic growth policies depends a lot on the infrastructure development. It is universally established that remote sensing and GIS tools play a major role in various...
Separating distributed source coding from network coding (2006)
Ramamoorthy, Aditya, Jain, Kamal, Chou, Philip A., Effros, Michelle
This correspondence considers the problem of distributed source coding of multiple sources over a network with multiple receivers. Each receiver seeks to reconstruct all of the original sources. The...
Polynomial time algorithms for multicast network code construction (2005)
Jaggi, Sidharth, Sanders, Peter, Chou, Philip A., Effros, Michelle, Egner, Sebastian, Jain, Kamal, ...
The famous max-flow min-cut theorem states that a source node s can send information through a network (V, E) to a sink node t at a rate determined by the min-cut separating s and t. Recently, it has...
Iterative Rounding 2-Approximation Algorithms (2004)
Lisa Fleischer, Kamal Jain, David P. Williamson
The survivable network design problem (SNDP) is the following problem: given an undirected graph and values r ij for each pair of vertices i and j, find a minimum-cost subgraph such that there are r...
A Primal-Dual Schema Based Approximation Algorithm for (2004)
Kamal Jain, Ion Mandoiu, Vijay V. Vazirani, David P. Williamson
The element connectivity problem falls in the category of survivable network design problems -- it is intermediate to the versions that ask for edge-disjoint and vertex-disjoint paths. The edge...
Achievable Throughput for Multiple Multicast (2004)
Yunnan Wu, Philip A. Chou, Qian Zhang, Kamal Jain, Wenwu Zhu, Sun-yuan Kung
In this paper, we investigate the throughput achievable for multiple multicast sessions in a wireless ad hoc network. We propose an iterative cross-layer optimization, which alternates between a...
Network Planning in Wireless Ad hoc (2004)
Yunnan Wu, Student Member, Philip A. Chou, Qian Zhang, Kamal Jain, Wenwu Zhu, ...
allocating information carrier supplies such that certain end-to-end communication demands, as a collection of multicast sessions, are fulfilled. This formulation necessitates a cross-layer coupling....
A Comparison of Network Coding and Tree Packing (2004)
Yunnan Wu, Philip A. Chou, Kamal Jain
We compare network coding solutions and routing solutions, namely packing distribution trees, for the problem of information multicast. To enable the comparison, we develop greedy tree packing...
Polynomial Time Algorithms for Multicast Network Code Construction (2003)
Sidharth Jaggi, Peter Sanders, Philip A. Chou, Sebastian Egner, Kamal Jain, Ludo Tolhuizen
The famous max-ow min-cut theorem states that a source node s can send information through a network (V; E) to a sink node t at a rate determined by the min-cut separating s and t. Recently it has...
Impact of Interference on Multi-hop Wireless Network (2003)
Kamal Jain, Jitendra Padhye, Venkat Padmanabhan, Lili Qiu
In this paper, we address the following question: given a speci c placement of wireless nodes in physical space and a speci c trac workload, what is the maximum throughput that can be supported by...
Low Complexity Algebraic Multicast Network Codes (2003)
Sidharth Jaggi, Philip A. Chou, Kamal Jain
We present a low complexity algorithm for designing algebraic codes that achieve the information theoretic capacity for the multicast problem on directed acyclic networks. These codes operate over...
Approximating Market Equilibria (2003)
In this paper we consider the classic problem of finding the market equilibrium prices under linear utility functions. A notion of approximate market equilibrium was proposed by Deng, Papadimitriou...
Low Complexity Algebraic Multicast Network Codes (2003)
Sidharth Jaggi, Philip A. Chou, Kamal Jain
We present a low complexity algorithm for designing algebraic codes that achieve the information theoretic capacity for the multicast problem on directed acyclic networks.
Kamal Jain, Mohammad Mahdian, Mohammad R. Salavatipour
The Steiner packing problem is to find the maximum number of edge-disjoint subgraphs of a given graph G that connect a given set of required points S. This problem is motivated by practical...
Greedy Facility Location Algorithms (2002)
Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, Vijay V. Vazirani
In this paper, we will formalize the method of dual tting and the idea of factor-revealing LP.
Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP (2002)
Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, Vijay V. Vazirani
In this paper, we will formalize the method of dual fitting and the idea of factor-revealing LP.
Kamal Jain, Mohammad Mahdian, Mohammad R. Salavatipour
The Steiner packing problem is to find the maximum number of edge-disjoint subgraphs of a given graph G that connect a given set of required points S. This problem is motivated by practical...
Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP (2002)
Jain, Kamal, Mahdian, Mohammad, Markakis, Evangelos, Saberi, Amin, Vazirani, Vijay V.
In this paper, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated...
Equitable Cost Allocations via Primal-Dual-Type Algorithms (2002)
Perhaps the strongest notion of truth-revealing in a cost sharing method is group strategyproofness. However, matters are not so clear-cut on fairness, and many dierent, sometimes even conicting,...
Enhancing Techniques in LP Based Approximation Algorithms (2002)
Kamal Jain, Richard A. Duke, Kalomire-eleni Mihail, George L. Nemhauser, Leonard J. Schulman
nts between every pair of vertices. We are asked to find a least cost subgraph such that every pair of vertices is connected with at least as many edge disjoint paths as their connectivity...
An Approximation Algorithm for the Fault (2002)
We consider a fault tolerant version of the metric facility location problem in which every city, j, is required to be connected to r j facilities. We give the first non-trivial approximation...
Approximation Algorithms for Metric (2002)
We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of...
A New Greedy Approach for Facility Location Problems (2002)
Kamal Jain, Mohammad Mahdian, Amin Saberi
We present a simple and natural greedy algorithm for the metric uncapacitated facility location problem achieving an approximation guarantee of 1.61 whereas the best previously known was 1.73.
An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem (2001)
Lisa Fleischer, Kamal Jain, David P. Williamson
In the edge connected version of this problem (EC-SNDP), these paths must be edge-disjoint. In the vertex connected version of the problem (VC-SNDP), the paths must be vertex disjoint. Jain et al....
Applications of Approximation Algorithms to Cooperative Games (2001)
this paper we will consider the problem of sharing the cost of a jointly utilized facility in a "fair" manner. Consider a service providing company whose set of possible customers, also called users,...
A New Greedy Approach for Facility Location Problems (2001)
Kamal Jain, Mohammad Mahdian, Amin Saberi
We present a natural greedy algorithm for the metric uncapacitated facility location problem achieving an approximation guarantee of 1.61 whereas the previously known best was 1.73. Using the...
Group Strategyproofness and No Subsidy via LP-Duality (2001)
We make two contributions to co-operative game theory, both of which rely heavily on linear programming duality theory. First, we introduce a fairness criterion on service providers, which we call No...
Testing Processes for Efficiency (2000)
Two notions for comparing the eciencies of equivalent concurrent systems have been developed and axiomatized in [1] and [2]. Recently Natarajan and Cleaveland have defined a notion of testing [6]...
A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem (2000)
Kamal Jain, Vijay V. Vazirani, David P. Williamson
The element connectivity problem falls in the category of survivable network design problems -- it is intermediate to the versions that ask for edge-disjoint and vertex-disjoint paths. The edge...
Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems (1999)
We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of...
Primal-Dual Approximation Algorithms for Metric Facility Location and (1999)
We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of...
Primal-Dual Approximation Algorithms for Metric Facility Location and (1999)
We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of...
Primal-Dual Approximation Algorithms for Metric Facility Location and (1999)
We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of...
Kamal Jain, Vijay V. Vazirani, David P. Williamson
The element connectivity problem falls in the category of survivable network design problems -- it is intermediate to the versions that ask for edge-disjoint and vertex-disjoint paths. The edge...
A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem (1998)
Kamal Jain, Vijay V. Vazirani, David P. Williamson
The element connectivity problem falls in the category of survivable network design problems -- it is intermediate to the versions that ask for edge-disjoint and vertex-disjoint paths. The edge...
Kamal Jain, Vijay V. Vazirani, David P. Williamson
The element connectivity problem falls in the category of survivable network design problems -- it is intermediate to the versions that ask for edge-disjoint and vertex-disjoint paths. The edge...
A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem (1998)
We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the...
The "Art of Trellis Decoding" is Computationally Hard - for Large Fields (1998)
Kamal Jain, Ion Mandoiu, Vijay V. Vazirani
The problem of minimizing the trellis complexity of a code by coordinate permutation is studied. Three measures of trellis complexity are considered: the total number of states, the total number of...
The "Art of Trellis Decoding" is Computationally Hard -- for Large Fields (1998)
Kamal Jain, Ion Mandoiu, Vijay V. Vazirani
The problem of minimizing the trellis complexity of a code by coordinate permutation is studied. Three measures of trellis complexity are considered: the total number of states, the total number of...
A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem (1998)
We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the...
A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem (1998)
Kamal Jain, Ion Mandoiu, Vijay V. Vazirani, David P. Williamson
The element connectivity problem falls in the category of survivable network design problems -- it is intermediate to the versions that ask for edge-disjoint and vertex-disjoint paths. The edge...
A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem (1998)
We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the...
A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem (1998)
Kamal Jain, Ion Mandoiu, Vijay V. Vazirani, David P. Williamson
The element connectivity problem falls in the category of survivable network design problems -- it is intermediate to the versions that ask for edge-disjoint and vertex-disjoint paths. The edge...
A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem (1998)
Kamal Jain, Ion Mandoiu, Vijay V. Vazirani, David P. Williamson
The element connectivity problem falls in the category of survivable network design problems -- it is intermediate to the versions that ask for edge-disjoint and vertex-disjoint paths. The edge...
A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem (1998)
We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the...
A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem (1998)
We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the...
A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem (1998)
We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the...
The "Art of Trellis Decoding" is Computationally Hard -- for Large Fields (1997)
Kamal Jain, Ion Mandoiu, Vijay V. Vazirani
The problem of minimizing the trellis complexity of a code by coordinate permutation is studied. Three measures of trellis complexity are considered: the total number of states, the total number of...
The "Art of Trellis Decoding" is Computationally Hard -- for Large Fields (1997)
Kamal Jain, Ion Mandoiu, Vijay V. Vazirani
The problem of minimizing the trellis complexity of a code by coordinate permutation is studied. Three measures of complexity are considered: the total number of states, the total number of edges,...
The "Art of Trellis Decoding" is Computationally Hard -- for Large Fields (1997)
Kamal Jain, Ion Mandoiu, Vijay V. Vazirani
The problem of minimizing the trellis complexity of a code by coordinate permutation is studied. Three measures of complexity are considered: the total number of states, the total number of edges,...
The "Art of Trellis Decoding" is Computationally Hard -- for Large Fields (1997)
Kamal Jain, Ion Mandoiu, Vijay V. Vazirani
The problem of minimizing the trellis complexity of a code by coordinate permutation is studied. Three measures of complexity are considered: the total number of states, the total number of edges,...
Testing Processes for Efficiency (1997)
. Two notions for comparing the efficiencies of equivalent concurrent systems have been developed and axiomatized in [1] and [2]. Recently Natarajan and Cleaveland have defined a notion of testing...
Testing Processes for Efficiency (1997)
. Two notions for comparing the efficiencies of equivalent concurrent systems have been developed and axiomatized in [1] and [2]. Recently Natarajan and Cleaveland have defined a notion of testing...
Testing Processes for Efficiency (1997)
. Two notions for comparing the efficiencies of equivalent concurrent systems have been developed and axiomatized in [1] and [2]. Recently Natarajan and Cleaveland have defined a notion of testing...