Source author record

Sanjeev Saxena

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computer Science and Game Theory math.OC

Catalog footprint

Research overview

4works

3topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Edge colouring Game on Trees with maximum degree $Δ=4$

Consider the following game. We are given a tree $T$ and two players (say) Alice and Bob who alternately colour an edge of a tree (using one of $k$ colours). If all edges of the tree get coloured, then Alice wins else Bob wins. Game chromatic index of trees of is the smallest index $k$ for which there is a winning strategy for Alice. If the maximum degree of a node in tree is $Δ$ , Erdos et.al.[6], show that the game chromatic index is at least $Δ+1$ . The bound is known to be tight for all values of $Δ\neq 4$ . In this paper we show that for $Δ=4$ , even if Bob is allowed to skip a move, Alice can always choose an edge to colour and win the game for $k=Δ+1$ . Thus the game chromatic index of trees of maximum degree $4$ is also $5$ . Hence, game chromatic index of trees of maximum degree $Δ$ is $Δ+1$ for all $Δ\geq 2$ . Moreover,the tree can be preprocessed to allow Alice to pick the next edge to colour in $O(1)$ time. A result of independent interest is a linear time algorithm for on-line edge-deletion problem on trees.

preprint2020arXiv

On seat allocation problem with multiple merit lists

In this note, we present a simpler algorithm for joint seat allocation problem in case there are two or more merit lists. In case of two lists (the current situation for Engineering seats in India), the running time of the algorithm is proportional to sum of running time for two separate (delinked) allocations. The algorithm is straight forward and natural and is not (at least directly) based on deferred acceptance algorithm of Gale and Shapley. Each person can only move higher in his or her preference list. Thus, all steps of the algorithm can be made public. This will improve transparency and trust in the system.

preprint2016arXiv

A Still Simpler Way of Introducing the Interior-Point Method for Linear Programming

Linear programming is now included in algorithm undergraduate and postgraduate courses for computer science majors. We give a self-contained treatment of an interior-point method which is particularly tailored to the typical mathematical background of CS students. In particular, only limited knowledge of linear algebra and calculus is assumed.

preprint2015arXiv

Still Simpler Way of Introducing Interior-Point method for Linear Programming

Linear Programming is now included in Algorithm undergraduate and postgraduate courses for Computer Science majors. It is possible to teach interior-point methods directly with just minimal knowledge of Algebra and Matrices.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Sanjeev Saxena

Research overview

Is this your work?

4 publications

Edge colouring Game on Trees with maximum degree $Δ=4$

On seat allocation problem with multiple merit lists

A Still Simpler Way of Introducing the Interior-Point Method for Linear Programming

Still Simpler Way of Introducing Interior-Point method for Linear Programming

See the researcher in context

Building this map preview

Sanjeev Saxena

Research overview

Is this your work?

4 publications

Edge colouring Game on Trees with maximum degree Δ=4Δ=4Δ=4

On seat allocation problem with multiple merit lists

A Still Simpler Way of Introducing the Interior-Point Method for Linear Programming

Still Simpler Way of Introducing Interior-Point method for Linear Programming

See the researcher in context

Building this map preview

Edge colouring Game on Trees with maximum degree $Δ=4$