Source author record

Alexander Grigoriev

Alexander Grigoriev appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Discrete Mathematics hep-ph math.CO astro-ph Computer Science and Game Theory Data Structures and Algorithms math.OC

Catalog footprint

What is connected

9works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2023arXiv

Envy-free dynamic pricing schemes

A combinatorial market consists of a set of indivisible items and a set of agents, where each agent has a valuation function that specifies for each subset of items its value for the given agent. From an optimization point of view, the goal is usually to determine a pair of pricing and allocation of the items that provides an efficient distribution of the resources, i.e., maximizes the social welfare, or is as profitable as possible for the seller, i.e., maximizes the revenue. To overcome the weaknesses of mechanisms operating with static prices, a recent line of research has concentrated on dynamic pricing schemes. In this model, agents arrive in an unspecified sequential order, and the prices can be updated between two agent-arrivals. Though the dynamic setting is capable of maximizing social welfare in various scenarios, the assumption that the agents arrive one after the other eliminates the standard concept of fairness. In this paper, we study the existence of optimal dynamic prices under fairness constraints in unit-demand markets. We propose four possible notions of envy-freeness of different strength depending on the time period over which agents compare themselves to others: the entire time horizon, only the past, only the future, or only the present. For social welfare maximization, while the first definition leads to Walrasian equilibria, we give polynomial-time algorithms that always find envy-free optimal dynamic prices in the remaining three cases. In contrast, for revenue maximization, we show that the corresponding problems are APX-hard if the ordering of the agents is fixed. On the positive side, we give polynomial-time algorithms for the setting when the seller can choose the order in which agents arrive.

preprint2020arXiv

On the status sequences of trees

The status of a vertex $v$ in a connected graph is the sum of the distances from $v$ to all other vertices. The status sequence of a connected graph is the list of the statuses of all the vertices of the graph. In this paper we investigate the status sequences of trees. Particularly, we show that it is NP-complete to decide whether there exists a tree that has a given sequence of integers as its status sequence. We also present some results about trees whose status sequences are comprised of a few distinct numbers or many distinct numbers. In this direction, we provide a partial answer to a conjecture of Shang and Lin from 2011, showing that any status injective tree is unique among trees. Finally, we investigate how orbit partitions and equitable partitions relate to the status sequence.

preprint2016arXiv

Neutrino spin-flavor oscillations derived from the mass basis

We consider neutrino mixing and oscillations in presence of an arbitrary constant magnetic field with nonzero transversal $B_{\perp}$ and longitudinal $B_{\parallel}$ components with respect to the direction of neutrino propagation. The electromagnetic interaction of neutrinos is determined by diagonal and transition neutrino magnetic moments that are introduced for the neutrino mass states. Explicit expressions for the effective neutrino diagonal and transition magnetic moments for the flavor basis in terms of these values for the mass states are obtained. The effective evolution Hamiltonian for the flavor neutrino and the corresponding oscillation probability are derived. The role of the longitudinal magnetic field component is examined. In particular, it is shown that: 1) $B_{\parallel}$ coupled to the corresponding magnetic moments shifts the neutrino energy, and 2) in case of nonvanishing neutrino transition magnetic moments $B_{\parallel}$ produces an additional mixing between neutrino states, both in the mass and flavor neutrino bases.

preprint2015arXiv

High Multiplicity Scheduling with Switching Costs for few Products

We study a variant of the single machine capacitated lot-sizing problem with sequence-dependent setup costs and product-dependent inventory costs. We are given a single machine and a set of products associated with a constant demand rate, maximum loading rate and holding costs per time unit. Switching production from one product to another incurs sequencing costs based on the two products. In this work, we show that by considering the high multiplicity setting and switching costs, even trivial cases of the corresponding "normal" counterparts become non-trivial in terms of size and complexity. We present solutions for one and two products.

preprint2014arXiv

On low treewidth graphs and supertrees

Compatibility of unrooted phylogenetic trees is a well studied problem in phylogenetics. It asks to determine whether for a set of k input trees there exists a larger tree (called a supertree) that contains the topologies of all k input trees. When any such supertree exists we call the instance compatible and otherwise incompatible. It is known that the problem is NP-hard and FPT, although a constructive FPT algorithm is not known. It has been shown that whenever the treewidth of an auxiliary structure known as the display graph is strictly larger than the number of input trees, the instance is incompatible. Here we show that whenever the treewidth of the display graph is at most 2, the instance is compatible. Furthermore, we give a polynomial-time algorithm to construct a supertree in this case. Finally, we demonstrate both compatible and incompatible instances that have display graphs with treewidth 3, highlighting that the treewidth of the display graph is (on its own) not sufficient to determine compatibility.

preprint2013arXiv

Bidimensionality of Geometric Intersection Graphs

Let B be a finite collection of geometric (not necessarily convex) bodies in the plane. Clearly, this class of geometric objects naturally generalizes the class of disks, lines, ellipsoids, and even convex polygons. We consider geometric intersection graphs GB where each body of the collection B is represented by a vertex, and two vertices of GB are adjacent if the intersection of the corresponding bodies is non-empty. For such graph classes and under natural restrictions on their maximum degree or subgraph exclusion, we prove that the relation between their treewidth and the maximum size of a grid minor is linear. These combinatorial results vastly extend the applicability of all the meta-algorithmic results of the bidimensionality theory to geometrically defined graph classes.

preprint2013arXiv

Nearly Planar Graphs and λ-flat Graphs

A graph G is ξ-nearly planar if it can be embedded in the sphere so that each of its edges is crossed at most ξ times. The family of ξ-nearly planar graphs is widely extending the notion of planarity. We introduce an alternative parameterized graph family extending the notion of planarity, the λ-flat graphs, this time defined as powers of plane graphs in regard to a novel notion of distance, the wall-by-wall distance. We show that the two parameterized graph classes are parametrically equivalent.

preprint2009arXiv

Spin light mode of massive neutrino radiative decay in matter

Using the exact solutions for the Dirac neutrino wave function in presence of matter we study the spin light mode in the process of neutrino transition from initial heavier to final lighter state. The spin light is emitted due to the neutrino nonzero transitional magnetic moment.

preprint2004arXiv

Spin light of neutrino in gravitational fields

We predict a new mechanism for the spin light of neutrino ($SLν$) that can be emitted by a neutrino moving in gravitational fields. This effect is studied on the basis of the quasiclassical equation for the neutrino spin evolution in a gravitational field. It is shown that the gravitational field of a rotating object, in the weak-field limit, can be considered as an axial vector external field which induces the neutrino spin procession. The corresponding probability of the neutrino spin oscillations in the gravitational field has been derived for the first time. The considered in this paper $SLν$ can be produced in the neutrino spin-flip transitions in gravitational fields. It is shown that the total power of this radiation is proportional to the neutrino gamma factor to the fourth power, and the emitted photon energy, for the case of an ultra relativistic neutrino, could span up to gamma-rays. We investigate the $SLν$ caused by both gravitational and electromagnetic fields, also accounting for effects of arbitrary moving and polarized matter, in various astrophysical environments. In particular, we discuss the $SLν$ emitted by a neutrino moving in the vicinity of a rotating neutron star, black hole surrounded by dense matter, as well as by a neutrino propagating in the relativistic jet from a quasar.