APAditya Pancholi
Aditya Pancholi
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Aditya Pancholi has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
- Neelima Gupta
Department of Computer Science, University of Delhi, Delhi, India
2 shared publications - Sapna Grover
Dyal Singh College, University of Delhi, IN
1 shared publication
Latest Publications
- Open Access
- 30 September 2018
- Published by Slovenian Association Informatika in Informatica
- Vol. 42 (3) , 401-405
Improved Local Search Based Approximation Algorithm for Hard Uniform Capacitated k-Median Problem
In this paper, we study the hard uniform capacitated $k$ - median problem. We give $(5+\epsilon)$ factor approximation for the problem using local search technique, violating cardinality by a factor of $3$. Though better results are known for the problem using LP techniques, local search algorithms are well known to be simpler. There is a trade-off viz-a-viz approximation factor and cardinality violation between our result and the result of Korupolu \etal \cite{KPR} which is the only result known for the problem using local search. They gave $(1 + \alpha)$ approximation factor with $(5 + 5/\alpha)$ factor loss in cardinality. In a sense, our result is an improvement as they violate the cardinality by more than a factor of $6$ to achieve $5$ factor in approximation. Though in their result, the approximation factor can be made arbitrarily small, cardinality loss is at least $5$ and small approximation factor is obtained at a big loss in cardinality. Thus, we improve upon their result with respect to cardinality.- 30 September 2018
- Published by Slovenian Association Informatika in Informatica
- Vol. 42 (3) , 401-405
Open AccessImproved Local Search Based Approximation Algorithm for Hard Uniform Capacitated k-Median Problem
In this paper, we study the hard uniform capacitated $k$ - median problem. We give $(5+\epsilon)$ factor approximation for the problem using local search technique, violating cardinality by a factor of $3$. Though better results are known for the problem using LP techniques, local search algorithms are well known to be simpler. There is a trade-off viz-a-viz approximation factor and cardinality violation between our result and the result of Korupolu \etal \cite{KPR} which is the only result known for the problem using local search. They gave $(1 + \alpha)$ approximation factor with $(5 + 5/\alpha)$ factor loss in cardinality. In a sense, our result is an improvement as they violate the cardinality by more than a factor of $6$ to achieve $5$ factor in approximation. Though in their result, the approximation factor can be made arbitrarily small, cardinality loss is at least $5$ and small approximation factor is obtained at a big loss in cardinality. Thus, we improve upon their result with respect to cardinality. - Open Access
Improved Local Search Based Approximation Algorithm for Hard Uniform Capacitated k-Median Problem
In this paper, we study the hard uniform capacitated $k$- median problem using local search heuristic. Obtaining a constant factor approximation for the \ckm problem is open. All the existing solutions giving constant-factor approximation, violate at least one of the cardinality and the capacity constraints. All except Koruplou et al are based on LP-relaxation. We give $(3+\epsilon)$ factor approximation algorithm for the problem violating the cardinality by a factor of $8/3 \approx 2.67$. There is a trade-off between the approximation factor and the cardinality violation between our work and the existing work. Koruplou et al gave $(1 + \alpha)$ approximation factor with $(5 + 5/\alpha)$ factor loss in cardinality using local search paradigm. Though the approximation factor can be made arbitrarily small, cardinality loss is at least $5$. On the other hand, we improve upon the results in [capkmGijswijtL2013],[capkmshili2014], [Lisoda2016] in terms of factor-loss though the cardinality loss is more in our case. Also, these results are obtained using LP-rounding, some of them being strengthened, whereas local search techniques are simple to apply and have been shown to perform well in practice via empirical studies. We extend the result to hard uniform capacitated $k$-median with penalties. To the best of our knowledge, ours is the first result for the problem.Open AccessImproved Local Search Based Approximation Algorithm for Hard Uniform Capacitated k-Median Problem
In this paper, we study the hard uniform capacitated $k$- median problem using local search heuristic. Obtaining a constant factor approximation for the \ckm problem is open. All the existing solutions giving constant-factor approximation, violate at least one of the cardinality and the capacity constraints. All except Koruplou et al are based on LP-relaxation. We give $(3+\epsilon)$ factor approximation algorithm for the problem violating the cardinality by a factor of $8/3 \approx 2.67$. There is a trade-off between the approximation factor and the cardinality violation between our work and the existing work. Koruplou et al gave $(1 + \alpha)$ approximation factor with $(5 + 5/\alpha)$ factor loss in cardinality using local search paradigm. Though the approximation factor can be made arbitrarily small, cardinality loss is at least $5$. On the other hand, we improve upon the results in [capkmGijswijtL2013],[capkmshili2014], [Lisoda2016] in terms of factor-loss though the cardinality loss is more in our case. Also, these results are obtained using LP-rounding, some of them being strengthened, whereas local search techniques are simple to apply and have been shown to perform well in practice via empirical studies. We extend the result to hard uniform capacitated $k$-median with penalties. To the best of our knowledge, ours is the first result for the problem.