Search

Your search keyword '"Khandekar, Rohit"' showing total 207 results
Start Over Author "Khandekar, Rohit"
207 results on '"Khandekar, Rohit"'

1. A Frequency Reconfigurable Antenna for Sub-GHz and TV White Space Applications

Author

Kumar, Sanjeev, Khandekar, Rohit, Rayavarapu, Neela, Angrisani, Leopoldo, Series Editor, Arteaga, Marco, Series Editor, Panigrahi, Bijaya Ketan, Series Editor, Chakraborty, Samarjit, Series Editor, Chen, Jiming, Series Editor, Chen, Shanben, Series Editor, Chen, Tan Kay, Series Editor, Dillmann, Rüdiger, Series Editor, Duan, Haibin, Series Editor, Ferrari, Gianluigi, Series Editor, Ferre, Manuel, Series Editor, Hirche, Sandra, Series Editor, Jabbari, Faryar, Series Editor, Jia, Limin, Series Editor, Kacprzyk, Janusz, Series Editor, Khamis, Alaa, Series Editor, Kroeger, Torsten, Series Editor, Liang, Qilian, Series Editor, Martín, Ferran, Series Editor, Ming, Tan Cher, Series Editor, Minker, Wolfgang, Series Editor, Misra, Pradeep, Series Editor, Möller, Sebastian, Series Editor, Mukhopadhyay, Subhas, Series Editor, Ning, Cun-Zheng, Series Editor, Nishida, Toyoaki, Series Editor, Pascucci, Federica, Series Editor, Qin, Yong, Series Editor, Seng, Gan Woon, Series Editor, Speidel, Joachim, Series Editor, Veiga, Germano, Series Editor, Wu, Haitao, Series Editor, Zhang, Junjie James, Series Editor, Merchant, S. N., editor, Warhade, Krishna, editor, and Adhikari, Debashis, editor

Published
2021
Full Text
View/download PDF

2. A Tight Algorithm for Strongly Connected Steiner Subgraph On Two Terminals With Demands

Author

Chitnis, Rajesh, Esfandiari, Hossein, Hajiaghayi, MohammadTaghi, Khandekar, Rohit, Kortsarz, Guy, and Seddighin, Saeed

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity, Computer Science - Discrete Mathematics
Abstract

Given an edge-weighted directed graph $G=(V,E)$ on $n$ vertices and a set $T=\{t_1, t_2, \ldots, t_p\}$ of $p$ terminals, the objective of the \scss ($p$-SCSS) problem is to find an edge set $H\subseteq E$ of minimum weight such that $G[H]$ contains an $t_{i}\rightarrow t_j$ path for each $1\leq i\neq j\leq p$. In this paper, we investigate the computational complexity of a variant of $2$-SCSS where we have demands for the number of paths between each terminal pair. Formally, the \sharinggeneral problem is defined as follows: given an edge-weighted directed graph $G=(V,E)$ with weight function $\omega: E\rightarrow \mathbb{R}^{\geq 0}$, two terminal vertices $s, t$, and integers $k_1, k_2$ ; the objective is to find a set of $k_1$ paths $F_1, F_2, \ldots, F_{k_1}$ from $s\leadsto t$ and $k_2$ paths $B_1, B_2, \ldots, B_{k_2}$ from $t\leadsto s$ such that $\sum_{e\in E} \omega(e)\cdot \phi(e)$ is minimized, where $\phi(e)= \max \Big\{|\{i\in [k_1] : e\in F_i\}|\ ,\ |\{j\in [k_2] : e\in B_j\}|\Big\}$. For each $k\geq 1$, we show the following: The \sharing problem can be solved in $n^{O(k)}$ time. A matching lower bound for our algorithm: the \sharing problem does not have an $f(k)\cdot n^{o(k)}$ algorithm for any computable function $f$, unless the Exponential Time Hypothesis (ETH) fails. Our algorithm for \sharing relies on a structural result regarding an optimal solution followed by using the idea of a "token game" similar to that of Feldman and Ruhl. We show with an example that the structural result does not hold for the \sharinggeneral problem if $\min\{k_1, k_2\}\geq 2$. Therefore \sharing is the most general problem one can attempt to solve with our techniques., Comment: To appear in Algorithmica. An extended abstract appeared in IPEC '14

Published
2015

4. Approximation Algorithms for Movement Repairmen

Author

Hajiaghayi, MohammadTaghi, Khandekar, Rohit, Khani, M. Reza, and Kortsarz, Guy

Subjects
Computer Science - Data Structures and Algorithms
Abstract

In the {\em Movement Repairmen (MR)} problem we are given a metric space $(V, d)$ along with a set $R$ of $k$ repairmen $r_1, r_2, ..., r_k$ with their start depots $s_1, s_2, ..., s_k \in V$ and speeds $v_1, v_2, ..., v_k \geq 0$ respectively and a set $C$ of $m$ clients $c_1, c_2, ..., c_m$ having start locations $s'_1, s'_2, ..., s'_m \in V$ and speeds $v'_1, v'_2, ..., v'_m \geq 0$ respectively. If $t$ is the earliest time a client $c_j$ is collocated with any repairman (say, $r_i$) at a node $u$, we say that the client is served by $r_i$ at $u$ and that its latency is $t$. The objective in the (\smr{}) problem is to plan the movements for all repairmen and clients to minimize the sum (average) of the clients latencies. The motivation for this problem comes, for example, from Amazon Locker Delivery \cite{amazon} and USPS gopost \cite{gopost}. We give the first $O(\log n)$-approximation algorithm for the \smr{} problem.

Published
2013

5. Combinatorial Algorithms for Capacitated Network Design

Author

Hajiaghayi, MohammadTaghi, Khandekar, Rohit, Kortsarz, Guy, and Nutov, Zeev

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We focus on designing combinatorial algorithms for the Capacitated Network Design problem (Cap-SNDP). The Cap-SNDP is the problem of satisfying connectivity requirements when edges have costs and hard capacities. We begin by showing that the Group Steiner tree problem (GST) is a special case of Cap-SNDP even when there is connectivity requirement between only one source-sink pair. This implies the first poly-logarithmic lower bound for the Cap-SNDP. We next provide combinatorial algorithms for several special cases of this problem. The Cap-SNDP is equivalent to its special case when every edge has either zero cost or infinite capacity. We consider a special case, called Connected Cap-SNDP, where all infinite-capacity edges in the solution are required to form a connected component containing the sinks. This problem is motivated by its similarity to the Connected Facility Location problem [G+01,SW04]. We solve this problem by reducing it to Submodular tree cover problem, which is a common generalization of Connected Cap-SNDP and Group Steiner tree problem. We generalize the recursive greedy algorithm [CEK] achieving a poly-logarithmic approximation algorithm for Submodular tree cover problem. This result is interesting in its own right and gives the first poly-logarithmic approximation algorithms for Connected hard capacities set multi-cover and Connected source location. We then study another special case of Cap-SNDP called Unbalanced point-to-point connection problem. Besides its practical applications to shift design problems [EKS], it generalizes many problems such as k-MST, Steiner Forest and Point-to-Point Connection. We give a combinatorial logarithmic approximation algorithm for this problem by reducing it to degree-bounded SNDP.

Published
2011

6. On Generalizations of Network Design Problems with Degree Bounds

Author

Bansal, Nikhil, Khandekar, Rohit, Konemann, Jochen, Nagarajan, Viswanath, and Peis, Britta

Subjects
Computer Science - Data Structures and Algorithms, F.2.2
Abstract

Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely, laminar crossing spanning tree), and (2) by incorporating `degree bounds' in other combinatorial optimization problems such as matroid intersection and lattice polyhedra. We give new or improved approximation algorithms, hardness results, and integrality gaps for these problems., Comment: v2, 24 pages, 4 figures

Published
2010
Full Text
View/download PDF

7. Fast Nearest Neighbor Search on Large Time-Evolving Graphs

Author

Akoglu, Leman, Khandekar, Rohit, Kumar, Vibhore, Parthasarathy, Srinivasan, Rajan, Deepak, Wu, Kun-Lung, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Goebel, Randy, Series editor, Tanaka, Yuzuru, Series editor, Wahlster, Wolfgang, Series editor, Siekmann, Jörg, Series editor, Calders, Toon, editor, Esposito, Floriana, editor, Hüllermeier, Eyke, editor, and Meo, Rosa, editor

Published
2014
Full Text
View/download PDF

8. A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)

Author

Chitnis, Rajesh Hemant, Esfandiari, Hossein, Hajiaghayi, MohammadTaghi, Khandekar, Rohit, Kortsarz, Guy, Seddighin, Saeed, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Cygan, Marek, editor, and Heggernes, Pinar, editor

Published
2014
Full Text
View/download PDF

9. On Fixed Cost k-Flow Problems

Author

Hajiaghayi, MohammadTaghi, Khandekar, Rohit, Kortsarz, Guy, Nutov, Zeev, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Kaklamanis, Christos, editor, and Pruhs, Kirk, editor

Published
2014
Full Text
View/download PDF

12. All-or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns

Author

Adany, Ron, Feldman, Moran, Haramaty, Elad, Khandekar, Rohit, Schieber, Baruch, Schwartz, Roy, Shachnai, Hadas, Tamir, Tami, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goemans, Michel, editor, and Correa, José, editor

Published
2013
Full Text
View/download PDF

13. Advantage of Overlapping Clusters for Minimizing Conductance

Author

Khandekar, Rohit, Kortsarz, Guy, Mirrokni, Vahab, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Fernández-Baca, David, editor

Published
2012
Full Text
View/download PDF

14. Network-Design with Degree Constraints

Author

Khandekar, Rohit, Kortsarz, Guy, Nutov, Zeev, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Goldberg, Leslie Ann, editor, Jansen, Klaus, editor, Ravi, R., editor, and Rolim, José D. P., editor

Published
2011
Full Text
View/download PDF

15. FLEX: A Slot Allocation Scheduling Optimizer for MapReduce Workloads

Author

Wolf, Joel, Rajan, Deepak, Hildrum, Kirsten, Khandekar, Rohit, Kumar, Vibhore, Parekh, Sujay, Wu, Kun-Lung, Balmin, Andrey, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Gupta, Indranil, editor, and Mascolo, Cecilia, editor

Published
2010
Full Text
View/download PDF

16. Budgeted Red-Blue Median and Its Generalizations

Author

Hajiaghayi, MohammadTaghi, Khandekar, Rohit, Kortsarz, Guy, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, de Berg, Mark, editor, and Meyer, Ulrich, editor

Published
2010
Full Text
View/download PDF

17. The Checkpoint Problem

Author

Hajiaghayi, MohammadTaghi, Khandekar, Rohit, Kortsarz, Guy, Mestre, Julián, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Serna, Maria, editor, Shaltiel, Ronen, editor, Jansen, Klaus, editor, and Rolim, José, editor

Published
2010
Full Text
View/download PDF

18. Prize-Collecting Steiner Network Problems

Author

Hajiaghayi, MohammadTaghi, Khandekar, Rohit, Kortsarz, Guy, Nutov, Zeev, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Eisenbrand, Friedrich, editor, and Shepherd, F. Bruce, editor

Published
2010
Full Text
View/download PDF

19. COLA: Optimizing Stream Processing Applications via Graph Partitioning

Author

Khandekar, Rohit, Hildrum, Kirsten, Parekh, Sujay, Rajan, Deepak, Wolf, Joel, Wu, Kun-Lung, Andrade, Henrique, Gedik, Buğra, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Bacon, Jean M., editor, and Cooper, Brian F., editor

Published
2009
Full Text
View/download PDF

20. On Hardness of Pricing Items for Single-Minded Bidders

Author

Khandekar, Rohit, Kimbrel, Tracy, Makarychev, Konstantin, Sviridenko, Maxim, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dinur, Irit, editor, Jansen, Klaus, editor, Naor, Joseph, editor, and Rolim, José, editor

Published
2009
Full Text
View/download PDF

21. A Fast and Simple Algorithm for Computing Market Equilibria

Author

Fleischer, Lisa, Garg, Rahul, Kapoor, Sanjiv, Khandekar, Rohit, Saberi, Amin, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Papadimitriou, Christos, editor, and Zhang, Shuzhong, editor

Published
2008
Full Text
View/download PDF

22. Two-Stage Robust Network Design with Exponential Scenarios

Author

Khandekar, Rohit, Kortsarz, Guy, Mirrokni, Vahab, Salavatipour, Mohammad R., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Halperin, Dan, editor, and Mehlhorn, Kurt, editor

Published
2008
Full Text
View/download PDF

23. Stateless Near Optimal Flow Control with Poly-logarithmic Convergence

Author

Awerbuch, Baruch, Khandekar, Rohit, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Laber, Eduardo Sany, editor, Bornstein, Claudson, editor, Nogueira, Loana Tito, editor, and Faria, Luerbio, editor

Published
2008
Full Text
View/download PDF

24. Offline Sorting Buffers on Line

Author

Khandekar, Rohit, Pandit, Vinayaka, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Asano, Tetsuo, editor

Published
2006
Full Text
View/download PDF

26. Price of Anarchy, Locality Gap, and a Network Service Provider Game

Author

Devanur, Nikhil, Garg, Naveen, Khandekar, Rohit, Pandit, Vinayaka, Saberi, Amin, Vazirani, Vijay, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Deng, Xiaotie, editor, and Ye, Yinyu, editor

Published
2005
Full Text
View/download PDF

28. Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries

Author

Garg, Naveen, Khandekar, Rohit, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Albers, Susanne, editor, and Radzik, Tomasz, editor

Published
2004
Full Text
View/download PDF

29. Bandwidth Maximization in Multicasting

Author

Garg, Naveen, Khandekar, Rohit, Kunal, Keshav, Pandit, Vinayaka, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Di Battista, Giuseppe, editor, and Zwick, Uri, editor

Published
2003
Full Text
View/download PDF

49. The Checkpoint Problem

Author

Hajiaghayi, MohammadTaghi, primary, Khandekar, Rohit, additional, Kortsarz, Guy, additional, and Mestre, Julián, additional

Published
2010
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results