Dr. Nikhil Kumar

2023 [ nach oben ]

Friedrich, Tobias; Issac, Davis; Kumar, Nikhil; Mallek, Nadym; Zeif, Ziena Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded TreewidthSymposium Theory of Computing (STOC) 2023: 1325–1334
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-\(r\) graph, there exists a (fractional) multicommodity flow of value \(f\), and a multicut of capacity \(c\) such that \(f leq c leq \mathcal{O(\ln(r + 1)) \cdot f \) . It is well known that the multiflow-multicut gap on an \(r\)-vertex (constant degree) expander graph can be \(\Omega(ln r)\), and hence our result is tight up to constant factors. Our proof is constructive, and we also obtain a polynomial time \( \mathcal{O(ln(r + 1))\)-approximation algorithm for the minimum multicut problem on treewidth-r graphs. Our algorithm proceeds by rounding the optimal fractional solution to the natural linear programming relaxation of the multicut problem. We introduce novel modifications to the well-known region growing algorithm to facilitate the rounding while guaranteeing at most a logarithmic factor loss in the treewidth.
@inproceedings{friedrich2023approximate, abstract = {We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-\(r\) graph, there exists a (fractional) multicommodity flow of value \(f\), and a multicut of capacity \(c\) such that \(f \leq c \leq \mathcal{O}(\ln(r + 1)) \cdot f \) . It is well known that the multiflow-multicut gap on an \(r\)-vertex (constant degree) expander graph can be \(\Omega(ln r)\), and hence our result is tight up to constant factors. Our proof is constructive, and we also obtain a polynomial time \( \mathcal{O}(ln(r + 1))\)-approximation algorithm for the minimum multicut problem on treewidth-r graphs. Our algorithm proceeds by rounding the optimal fractional solution to the natural linear programming relaxation of the multicut problem. We introduce novel modifications to the well-known region growing algorithm to facilitate the rounding while guaranteeing at most a logarithmic factor loss in the treewidth.}, author = {Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena}, booktitle = {Symposium Theory of Computing (STOC)}, keywords = {davisissac nadymmallek nikhilkumar stoc tobiasfriedrich year2023 zienazeif}, pages = {1325–1334}, title = {Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth}, year = 2023 }

2022 [ nach oben ]

Friedrich, Tobias; Issac, Davis; Kumar, Nikhil; Mallek, Nadym; Zeif, Ziena A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 GraphsApproximation Algorithms for Combinatorial Optimization Problems (APPROX) 2022: 55:1–55:18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value \(f\) with congestion \(4\), and a multicut of capacity \(c\) such that \(c \leq 20f \) . This implies a multiflow-multicut gap of \(80\) and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.
@inproceedings{friedrich2022primaldual, abstract = {We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value \(f\) with congestion \(4\), and a multicut of capacity \(c\) such that \(c \leq 20f \) . This implies a multiflow-multicut gap of \(80\) and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.}, author = {Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena}, booktitle = {Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}, keywords = {approx davisissac nadymmallek nikhilkumar tobiasfriedrich year2022 zienazeif}, pages = {55:1–55:18}, title = {A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs}, year = 2022 }

Kumar, Nikhil An Approximate Generalization of the Okamura-Seymour TheoremSymposium on Foundations of Computer Science (FOCS) 2022
[ Abstract ] [ BibTeX ] [ Download ]
 
We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing \(\Omega(1)\)-fraction of all the demands. To prove this, we give a \(L_1\)-embedding of the planar metric which approximately preserves distance between all pair of points on the same face.
@inproceedings{kumar2022approximate, abstract = {We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing \(\Omega(1)\)-fraction of all the demands. To prove this, we give a \(L_1\)-embedding of the planar metric which approximately preserves distance between all pair of points on the same face.}, author = {Kumar, Nikhil}, booktitle = {Symposium on Foundations of Computer Science (FOCS)}, keywords = {sys:relevantfor:ae focs nikhilkumar year2022}, title = {An Approximate Generalization of the Okamura-Seymour Theorem}, year = 2022 }

2021 [ nach oben ]

Antoniadis, Antonios; Kumar, Gunjan; Kumar, Nikhil Skeletons and Minimum Energy SchedulingInternational Symposium on Algorithms and Computation (ISAAC) 2021: 51:1–51:16
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Consider the problem where \(n\) jobs, each with a release time, a deadline and a required processing time are to be feasibly scheduled in a single- or multi-processor setting so as to minimize the total energy consumption of the schedule. A processor has two available states: a sleep state where no energy is consumed but also no processing can take place, and an active state which consumes energy at a rate of one, and in which jobs can be processed. Transitioning from the active to the sleep does not incur any further energy cost, but transitioning from the sleep to the active state requires \(q\) energy units. Jobs may be preempted and (in the multi-processor case) migrated. The single-processor case of the problem is known to be solvable in polynomial time via an involved dynamic program, whereas the only known approximation algorithm for the multi-processor case attains an approximation factor of 3 and is based on rounding the solution to a linear programming relaxation of the problem. In this work, we present efficient and combinatorial approximation algorithms for both the single- and the multi-processor setting. Before, only an algorithm based on linear programming was known for the multi-processor case. Our algorithms build upon the concept of a skeleton, a basic (and not necessarily feasible) schedule that captures the fact that some processor(s) must be active at some time point during an interval. Finally, we further demonstrate the power of skeletons by providing an 2-approximation algorithm for the multiprocessor case, thus improving upon the recent breakthrough 3-approximation result. Our algorithm is based on a novel rounding scheme of a linear-programming relaxation of the problem which incorporates skeletons.
@inproceedings{antoniadis2021skeletons, abstract = {Consider the problem where \(n\) jobs, each with a release time, a deadline and a required processing time are to be feasibly scheduled in a single- or multi-processor setting so as to minimize the total energy consumption of the schedule. A processor has two available states: a sleep state where no energy is consumed but also no processing can take place, and an active state which consumes energy at a rate of one, and in which jobs can be processed. Transitioning from the active to the sleep does not incur any further energy cost, but transitioning from the sleep to the active state requires \(q\) energy units. Jobs may be preempted and (in the multi-processor case) migrated. The single-processor case of the problem is known to be solvable in polynomial time via an involved dynamic program, whereas the only known approximation algorithm for the multi-processor case attains an approximation factor of 3 and is based on rounding the solution to a linear programming relaxation of the problem. In this work, we present efficient and combinatorial approximation algorithms for both the single- and the multi-processor setting. Before, only an algorithm based on linear programming was known for the multi-processor case. Our algorithms build upon the concept of a skeleton, a basic (and not necessarily feasible) schedule that captures the fact that some processor(s) must be active at some time point during an interval. Finally, we further demonstrate the power of skeletons by providing an 2-approximation algorithm for the multiprocessor case, thus improving upon the recent breakthrough 3-approximation result. Our algorithm is based on a novel rounding scheme of a linear-programming relaxation of the problem which incorporates skeletons.}, author = {Antoniadis, Antonios and Kumar, Gunjan and Kumar, Nikhil}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {isaac nikhilkumar year2021}, pages = {51:1-51:16}, title = {Skeletons and Minimum Energy Scheduling}, year = 2021 }

2020 [ nach oben ]

Das, Syamantak; Jain, Lavina; Kumar, Nikhil A Constant Factor Approximation for Capacitated Min-Max Tree CoverApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) 2020: 55:1–55:13
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Given a graph \(G=(V,E)\) with non-negative real edge lengths and an integer parameter \(k\), the (uncapacitated) Min-Max Tree Cover problem seeks to find a set of at most \(k\) trees which together span \(V\) and each tree is a subgraph of \(G\). The objective is to minimize the maximum length among all the trees. In this paper, we consider a capacitated generalization of the above and give the first constant factor approximation algorithm. In the capacitated version, there is a hard uniform capacity (\(\lambda\)) on the number of vertices a tree can cover. Our result extends to the rooted version of the problem, where we are given a set of \(k\) root vertices, \(R\) and each of the covering trees is required to include a distinct vertex in \(R\) as the root. Prior to our work, the only result known was a \((2k-1)\)-approximation algorithm for the special case when the total number of vertices in the graph is \(k\lambda\) [Guttmann-Beck and Hassin, J. of Algorithms, 1997]. Our technique circumvents the difficulty of using the minimum spanning tree of the graph as a lower bound, which is standard for the uncapacitated version of the problem [Even et al., OR Letters 2004],[Khani et al., Algorithmica 2010]. Instead, we use Steiner trees that cover \(\lambda\) vertices along with an iterative refinement procedure that ensures that the output trees have low cost and the vertices are well distributed among the trees.
@inproceedings{das2020constant, abstract = {Given a graph \(G=(V,E)\) with non-negative real edge lengths and an integer parameter \(k\), the (uncapacitated) Min-Max Tree Cover problem seeks to find a set of at most \(k\) trees which together span \(V\) and each tree is a subgraph of \(G\). The objective is to minimize the maximum length among all the trees. In this paper, we consider a capacitated generalization of the above and give the first constant factor approximation algorithm. In the capacitated version, there is a hard uniform capacity (\(\lambda\)) on the number of vertices a tree can cover. Our result extends to the rooted version of the problem, where we are given a set of \(k\) root vertices, \(R\) and each of the covering trees is required to include a distinct vertex in \(R\) as the root. Prior to our work, the only result known was a \((2k-1)\)-approximation algorithm for the special case when the total number of vertices in the graph is \(k\lambda\) [Guttmann-Beck and Hassin, J. of Algorithms, 1997]. Our technique circumvents the difficulty of using the minimum spanning tree of the graph as a lower bound, which is standard for the uncapacitated version of the problem [Even et al., OR Letters 2004],[Khani et al., Algorithmica 2010]. Instead, we use Steiner trees that cover \(\lambda\) vertices along with an iterative refinement procedure that ensures that the output trees have low cost and the vertices are well distributed among the trees.}, author = {Das, Syamantak and Jain, Lavina and Kumar, Nikhil}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM)}, keywords = {approx lavinajain nikhilkumar syamantakdas year2020}, pages = {55:1-55:13}, title = {A Constant Factor Approximation for Capacitated Min-Max Tree Cover}, volume = 176, year = 2020 }

Garg, Naveen; Kumar, Nikhil Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral FlowEuropean Symposium on Algorithms (ESA) 2020: 55:1–55:13
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Given an edge weighted graph and a forest \(F\), the em 2-edge connectivity augmentation problem is to pick a minimum weighted set of edges, \(E'\), such that every connected component of \(E'\cup F\) is 2-edge connected. Williamson et al. gave a 2-approximation algorithm (WGMV) for this problem using the primal-dual schema. We show that when edge weights are integral, the WGMV procedure can be modified to obtain a half-integral dual. The 2-edge connectivity augmentation problem has an interesting connection to routing flow in graphs where the union of supply and demand is planar. The half-integrality of the dual leads to a tight 2-approximate max-half-integral-flow min-multicut theorem.
@inproceedings{garg2020halfintegrality, abstract = {Given an edge weighted graph and a forest \(F\), the {\em 2-edge connectivity augmentation problem} is to pick a minimum weighted set of edges, \(E'\), such that every connected component of \(E'\cup F\) is 2-edge connected. Williamson et al. gave a 2-approximation algorithm (WGMV) for this problem using the primal-dual schema. We show that when edge weights are integral, the WGMV procedure can be modified to obtain a half-integral dual. The 2-edge connectivity augmentation problem has an interesting connection to routing flow in graphs where the union of supply and demand is planar. The half-integrality of the dual leads to a tight 2-approximate max-half-integral-flow min-multicut theorem.}, author = {Garg, Naveen and Kumar, Nikhil}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {esa naveengarg nikhilkumar year2020}, pages = {55:1-55:13}, title = {Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow}, volume = 173, year = 2020 }

Garg, Naveen; Kumar, Nikhil; Sebö, András Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-ApproximationInteger Programming and Combinatorial Optimization (IPCO) 2020: 144–157
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. We consider instances where the union of the supply and demand graphs is planar and prove that there exists a multiflow of value at least half the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer flow of value at least half the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing at most half the value thus providing a 1/4-approximation algorithm and integrality gap for maximum integer multiflows in the plane.
@inproceedings{garg2020integer, abstract = {In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. We consider instances where the union of the supply and demand graphs is planar and prove that there exists a multiflow of value at least half the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer flow of value at least half the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing at most half the value thus providing a 1/4-approximation algorithm and integrality gap for maximum integer multiflows in the plane.}, author = {Garg, Naveen and Kumar, Nikhil and Sebö, András}, booktitle = {Integer Programming and Combinatorial Optimization (IPCO)}, keywords = {andrassebo ipco naveengarg nikhilkumar year2020}, pages = {144-157}, title = {Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation}, volume = 12125, year = 2020 }

Kumar, Nikhil Multicommodity Flows in Planar Graphs with Demands on FacesInternational Symposium on Algorithms and Computation (ISAAC) 2020: 1–11
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We consider the problem of multicommodity flows in planar graphs. Seymour showed that if the union of supply and demand graphs is planar, then the cut condition is also sufficient for routing demands. Okamura-Seymour showed that if the supply graph is planar and all demands are incident on one face, then again the cut condition is sufficient for routing demands. We consider a common generalization of these settings where the end points of each demand are on the same face of the planar graph. We show that if the source sink pairs on each face of the graph are such that sources and sinks appear contiguously on the cycle bounding the face, then the flow cut gap is at most 3. We come up with a notion of approximating demands on a face by convex combination of laminar demands to prove this result.
@inproceedings{kumar2020multicommodity, abstract = {We consider the problem of multicommodity flows in planar graphs. Seymour showed that if the union of supply and demand graphs is planar, then the cut condition is also sufficient for routing demands. Okamura-Seymour showed that if the supply graph is planar and all demands are incident on one face, then again the cut condition is sufficient for routing demands. We consider a common generalization of these settings where the end points of each demand are on the same face of the planar graph. We show that if the source sink pairs on each face of the graph are such that sources and sinks appear contiguously on the cycle bounding the face, then the flow cut gap is at most 3. We come up with a notion of approximating demands on a face by convex combination of laminar demands to prove this result.}, author = {Kumar, Nikhil}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {isaac nikhilkumar year2020}, pages = {1-11}, title = {Multicommodity Flows in Planar Graphs with Demands on Faces}, year = 2020 }

Antoniadis, Antonios; Garg, Naveen; Kumar‎, Gunjan; Kumar, Nikhil Parallel Machine Scheduling to Minimize Energy ConsumptionSymposium on Discrete Algorithms (SODA) 2020: 2758–2769
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Given \(n\) jobs with release dates, deadlines and processing times we consider the problem of scheduling them on \(m\) parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires \(L\) units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem.
@inproceedings{antoniadis2020parallel, abstract = {Given \(n\) jobs with release dates, deadlines and processing times we consider the problem of scheduling them on \(m\) parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires \(L\) units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem.}, author = {Antoniadis, Antonios and Garg, Naveen and Kumar‎, Gunjan and Kumar, Nikhil}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {antoniosantoniadis gunjankumar naveengarg nikhilkumar soda year2020}, pages = {2758-2769}, title = {Parallel Machine Scheduling to Minimize Energy Consumption}, year = 2020 }

2019 [ nach oben ]

Batra, Sanjit Singh; Kumar, Nikhil; Tripathi, Amitabha Some Problems Concerning the Frobenius Number for Extensions of an Arithmetic ProgressionThe Ramanujan Journal 2019: 545–565
[ Abstract ] [ BibTeX ] [ Download ]
 
For positive and relative prime set of integers \(A=\{a_1,\ldots,a_k\}\), let \(\Gamma(A)\) denote the set of integers of the form \(a_1 x_1+ \ldots +a_k x_k\) with each \(x_i \geq 0\). It is well known that \(\Gamma^c(A)=\mathbb{N setminus \Gamma(A)\) is a finite set, so that \(\texttt{g(A)\), which denotes the largest integer in \(\Gamma^{c(A)\), is well defined. Let \(A=AP(a,d,k)\) denote the set \(\{ a,a+d, dots, a+(k-1)d \}\) of integers in arithmetic progression, and let \(\texttt{gcd(a,d)=1\). We (i) determine the set \(A^+=\{ b in \Gamma^c(A):\texttt{g(A \cup \ b \})= \texttt{g(A) \}\); (ii) determine a subset \(\overline{A^{+}}\) of \(\Gamma^{c(A)\) of largest cardinality such that \(A \cup \overline{A^{+}}\) is an independent set and \(\texttt{g(A \cup \overline{A^{+}})=\texttt{g(A)\); and (iii) determine \(\texttt{g(A \cup \{b\})\) for some class of values of \(b\) that includes results of some recent work.
@article{batra2019problems, abstract = {For positive and relative prime set of integers \(A=\{a_1,\ldots,a_k\}\), let \(\Gamma(A)\) denote the set of integers of the form \(a_1 x_1+ \ldots +a_k x_k\) with each \(x_i \geq 0\). It is well known that \(\Gamma^c(A)=\mathbb{N} \setminus \Gamma(A)\) is a finite set, so that \(\texttt{g}(A)\), which denotes the largest integer in \(\Gamma^{c}(A)\), is well defined. Let \(A=AP(a,d,k)\) denote the set \(\{ a,a+d, \dots, a+(k-1)d \}\) of integers in arithmetic progression, and let \(\texttt{gcd}(a,d)=1\). We (i) determine the set \(A^+=\{ b \in \Gamma^c(A):\texttt{g}(A \cup \{ b \})= \texttt{g}(A) \}\); (ii) determine a subset \(\overline{A^{+}}\) of \(\Gamma^{c}(A)\) of largest cardinality such that \(A \cup \overline{A^{+}}\) is an independent set and \(\texttt{g}(A \cup \overline{A^{+}})=\texttt{g}(A)\); and (iii) determine \(\texttt{g}(A \cup \{b\})\) for some class of values of \(b\) that includes results of some recent work.}, author = {Batra, Sanjit Singh and Kumar, Nikhil and Tripathi, Amitabha}, journal = {The Ramanujan Journal}, keywords = {amitabhatripathi nikhilkumar ramanujan sanjitsinghbartra year2018}, pages = {545-565}, title = {Some Problems Concerning the Frobenius Number for Extensions of an Arithmetic Progression}, volume = 48, year = 2019 }

2015 [ nach oben ]

Batra, Sanjit Singh; Kumar, Nikhil; Tripathi, Amitabha On a Linear Diophantine Problem Involving the Fibonacci and Lucas SequencesIntegers 2015: A26
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
For a positive and relatively prime set \(A\), let \(\Gamma(A)\) denote the set of integers that are formed by taking nonnegative integer linear combinations of integers in \(A\). Then there are finitely many positive integers that do not belong to \(\Gamma(A)\). For \(A\), let \(\texttt{g(A)\) and \(\texttt{n(A)\) denote the largest integer and the number of integers that do not belong to \(\Gamma(A)\), respectively. We determine both \(\texttt{g(A)\) and \(\texttt{n(A)\) for two sets that arise naturally from the Fibonacci sequence and the Lucas sequence.
@article{batra2015linear, abstract = {For a positive and relatively prime set \(A\), let \(\Gamma(A)\) denote the set of integers that are formed by taking nonnegative integer linear combinations of integers in \(A\). Then there are finitely many positive integers that do not belong to \(\Gamma(A)\). For \(A\), let \(\texttt{g}(A)\) and \(\texttt{n}(A)\) denote the largest integer and the number of integers that do not belong to \(\Gamma(A)\), respectively. We determine both \(\texttt{g}(A)\) and \(\texttt{n}(A)\) for two sets that arise naturally from the Fibonacci sequence and the Lucas sequence.}, author = {Batra, Sanjit Singh and Kumar, Nikhil and Tripathi, Amitabha}, journal = {Integers}, keywords = {amitabhatripathi integers nikhilkumar sanjitsinghbartra year2015}, pages = {A26}, title = {On a Linear Diophantine Problem Involving the Fibonacci and Lucas Sequences}, volume = 15, year = 2015 }