Russian President Dmitry Medvedev agreed on Wednesday to meet his new Ukrainian counterpart Viktor Yanukovych in Kiev this May to continue work to improve ties between the two states, the Kremlin said.

The decision was made during a telephone conversation between Medvedev and Yanukovych.

"The heads of states have discussed the first step towards implementing the important agreements reached during a recent high-level Russian-Ukrainian meeting in Moscow and outlined tasks for further work in this direction," the statement said.

During his visit to the Ukrainian capital, the Russian leader will take part in a meeting of the Russian-Ukrainian Interstate Commission, the statement said.

Ties between Moscow and Kiev, which deteriorated during the pro-Western presidency of Viktor Yushchenko, have improved since Yanukovych won the Ukrainian presidential runoff in February.

The new Ukrainian leader has pledged to hold more balanced relations with Russia than Yushchenko, whose policies, including a bid for NATO membership, frequently infuriated Moscow.

Yanukovych, who was sworn in as Ukraine's president on February 25, visited Moscow on March 5 to discuss bilateral cooperation with Medvedev and Russian Prime Minister Vladimir Putin.

Medvedev and Yanukovych promised to improve ties between Moscow and Kiev and agreed to establish an interstate commission to achieve this goal.

Yanukovych also proposed that the new nuclear arms reduction treaty between Russia and the United States be signed in Kiev.

On Tuesday, after a meeting with the new Ukrainian Foreign Minister, Kostyantyn Hryshchenko, in Moscow, Russian Foreign Minister Sergei Lavrov said Russia would be "happy" to sign the treaty in the Ukrainian capital but that the decision should be taken by the Russian and U.S. presidents.

Earlier, Yanukovych confirmed his participation in an informal CIS summit due in Moscow on May 8.

MOSCOW, March 17 (RIA Novosti)