Search

Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard, which settles an open question.

The rapid development of neutrino astronomy, which is expressed, among other things, in the emergence of new neutrino mega-projects capable of efficient registering astrophysical neutrino fluxes requires a detailed knowledge of neutrino evolution inside neutrino sources (type II supernovae, gamma-ray bursts). This evolution can be influenced by many factors, each should be accounted for by a relevant theory. In this work, we develop the theory of neutrino propagation in moving and/or polarized matter by introducing for the first time an exact spin integral of motion. This enables us to obtain the neutrino dispersion under these conditions and resolve it for most important cases. Our approach opens up the possibility to consistently classify neutrino states in moving and/or polarized medium and, as a consequence, to give a systematic description of the related physical phenomena (e.g., neutrino oscillations, neutrino electromagnetic radiation)., Comment: 4 pages, based on the presentation at the 41st International Conference on High Energy Physics (ICHEP2022 6-13 July 2022, Bologna, Italy), prepared for the ICHEP2022 proceedings

Healthy nutrition promotions and regulations have long been regarded as a tool for increasing social welfare. One of the avenues taken in the past decade is sugar consumption regulation by introducing a sugar tax. Such a tax increases the price of extensive sugar containment in products such as soft drinks. In this article we consider a typical problem of optimal regulatory policy design, where the task is to determine the sugar tax rate maximizing the social welfare. We model the problem as a sequential game represented by the three-level mathematical program. On the upper level, the government decides upon the tax rate. On the middle level, producers decide on the product pricing. On the lower level, consumers decide upon their preferences towards the products. While the general problem is computationally intractable, the problem with a few product types is polynomially solvable, even for an arbitrary number of heterogeneous consumers. This paper presents a simple, intuitive and easily implementable framework for computing optimal sugar tax in a market with a few products. This resembles the reality as the soft drinks, for instance, are typically categorized in either regular or no-sugar drinks, e.g. Coca-Cola and Coca-Cola Zero. We illustrate the algorithm using an example based on the real data and draw conclusions for a specific local market.

Since summer 2007, mobile phone users in the European Union (EU) are protected by a ceiling on the roaming tariff when calling or receiving a call abroad. We analyze the effects of this price regulative policy, and compare it to alternative implementations of price regulations. The problem is a three-level mathematical program: The EU determines the price regulative policy, the telephone operator sets profit-maximizing prices, and customers choose to accept or decline the operator’s offer. The first part of this paper contains a polynomial time algorithm to solve such a three-level program. The crucial idea is to partition the polyhedron of feasible price regulative parameters into a polynomial number of smaller polyhedra such that a certain mprimitive decision problem can be written as an LP on each of those. Then the problem can be solved by a combination of enumeration and linear programming. In the second part, we analyze more specifically an instance of this problem, namely the price regulation problem that the EU encounters. Using customer-data from a large telephone operator, we compare different price regulative policies with respect to their social welfare. On the basis of the specific social welfare function, we observe that other price regulative policies or different ceilings can improve the total social welfare.

We consider a revenue maximization problem where we are selling a set of items, each available in a certain quantity, to a set of bidders. Each bidder is interested in one or several bundles of items. We assume the bidders’ valuations for each of these bundles to be known. Whenever bundle prices are determined by the sum of single item prices, this algorithmic problem was recently shown to be inapproximable to within a semi-logarithmic factor. We consider two scenarios for determining bundle prices that allow to break this inapproximability barrier. Both scenarios are motivated by problems where items are different, yet comparable. First, we consider classical single item prices with an additional monotonicity constraint, enforcing that larger bundles are at least as expensive as smaller ones. We show that the problem remains strongly NP-hard, and we derive a PTAS. Second, motivated by real-life cases, we introduce the notion of affine price functions, and derive fixed-parameter polynomial time algorithms.

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.

In this paper we consider an ILP-based approach to tackle the problem of determining a treewidth of the graph. We give an overview of existing attempts and develop further LP-based techniques for the problem. We present two different ILP formulations for the treewidth. To obtain the first one we merge the chordalization-based ILP by Koster and Bodlaender and flow metrics approach by Bornstein and Vempala. The second brand-new ILP is based on the structural properties of the tree-decomposition. It has a nice application of the local branching techniques by Fischetti and Lodi.

This paper addresses two-dimensional trajectory optimization problems, where the mover''s speed monotonically decreases/increases in one of the space''s coordinates. For instance, it is well-known that the absolute value of the helicopter speed decreases in altitude because air pressure drops. Then, it is not trivial to find a time-minimal helicopter trajectory from one given point to another. We address such problems in different settings for the medium (atmosphere) and in the presence of obstacles. First, we consider the basic problem without any obstacles, where the mover''s speed decreases linearly in altitude. We show that the problem is reducible to the L''Hopital problem, one of the well-studied problems in geometrical optics. In this case, the time-optimal trajectory is a circular segment, and therefore can be expressed in a closed analytic form. Next, we adress the problem with linear speed decrease in presence of rectilinear obstacles. We show that this problem can be solved in polynomial time. Finally, we consider the case without obstacles, where the medium is non-uniform and the mover''s velocity is a piece-wise linear concave monotonically decreasing function. This is a widely accepted model in our motivating application of helicopter flights. In this case, we reduce the problem to the solution of a system of polynomial equations of fixed degree. Here, if the number of breakpoints of the velocity function is a constant, the algebraic elimination theory allows us to solve the problem in constant time with any given level of precision.

We consider the problem of pricing items in order to maximize the revenue obtainable from a set of single minded customers. We relate the tractability of the problem to structural properties of customers' valuations: the problem admits an effcient approximation algorithm, parameterized along the inhomogeneity of the valuations.

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., Comment: to appear in the proceedings of the 21st Rencontres de Blois (France), June 21-26, 2009

The highway pricing problem asks for prices to be determined for segments of a single highway such as to maximize the revenue obtainable from a given set of customers with known valuations. The problem is (weakly) NP-hard and a recent quasi-PTAS suggests that a PTAS might be in reach. Yet, so far it has resisted any attempt for constant-factor approximation algorithms. We relate the tractability of the problem to structural properties of customers' valuations. We show that the problem becomes NP-hard as soon as the average valuations of customers are not homogeneous, even under further restrictions such as monotonicity. Moreover, we derive an efficient approximation algorithm, parameterized along the inhomogeneity of customers' valuations. Finally, we discuss extensions of our results that go beyond the highway pricing problem.

The highway pricing problem asks for prices to be determined for segments of a single highway such as to maximize the revenue obtainable from a given set of customers with known valuations. The problem is (weakly) NP-hard and a recent quasi-PTAS suggests that a PTAS might be in reach. Yet, so far it has resisted any attempt for constant-factor approximation algorithms. We relate the tractability of the problem to structural properties of customers'' valuations. We show that the problem becomes NP-hard as soon as the average valuations of customers are not homogeneous, even under further restrictions such as monotonicity. Moreover, we derive an efficient approximation algorithm, parameterized along the inhomogeneity of customers'' valuations. Finally, we discuss extensions of our results that go beyond the highway pricing problem.

We consider a profit maximization problem where we are asked to price a set of m items that are to be assigned to a set of n customers. The items can be represented as the edges of an undirected (multi)graph G, where an edge multiplicity larger than one corresponds to multiple copies of the same item. Each customer is interested in purchasing a bundle of edges of G, and we assume that each bundle forms a simple path in G. Each customer has a known budget for her respective bundle, and is interested only in that particular bundle. The goal is to determine item prices and a feasible assignment of items to customers in order to maximize the total profit. When the underlying graph G is a path, we derive a fully polynomial time approximation scheme, complementing a recent NP-hardness result. If the underlying graph is a tree, and edge multiplicities are one, we show that the problem is polynomially solvable, contrasting its APX-hardness for the case of unlimited availability of items. However, if the underlying graph is a grid, and edge multiplicities are one, we show that it is even NP-complete to approximate the maximum profit to within a factor n 1 − − ε.

A short review of the properties of the spin light of neutrino ($SL\nu$) in matter, supplied with some historical notes on the discussed subject, is given. It is shown that consideration of the $SL\nu$ in matter in hep-ph/0605114 is based on erroneous calculations which ignore the fact that the energy-momentum conservation law can not be violated for this process. An attempt to rename the $SL\nu$ in matter, undertaken in hep-ph/0606262, is groundless., Comment: 6 pages, contribution to the Proceedings of the 14th International Seminar on High Energy Physics "Quarks-2006" (St.-Petersburg, Repino, May 19-25, 2006); v2: a typo corrected

We consider a revenue maximization problem where we are selling a set of m items, each of which available in a certain quantity (possibly unlimited) to a set of n bidders. Bidders are single minded, that is, each bidder requests exactly one subset, or bundle of items. Each bidder has a valuation for the requested bundle that we assume to be known to the seller. The task is to find an envy-free pricing such as to maximize the revenue of the seller. We derive several complexity results and algorithms for several variants of this pricing problem. In fact, the settings that we consider address problems where the different items are `homogeneous'' in some sense. First, we introduce the notion of affne price functions that can be used to model situations much more general than the usual combinatorial pricing model that is mostly addressed in the literature. We derive fixed-parameter polynomial time algorithms as well as inapproximability results. Second, we consider the special case of combinatorial pricing, and introduce a monotonicity constraint that can also be seen as `global'' envy-freeness condition. We show that the problem remains strongly NP-hard, and we derive a PTAS - thus breaking the inapproximability barrier known for the general case. As a special case, we finally address the notorious highway pricing problem under the global envy-freeness condition.

We consider a scheduling problem where a set of jobs is distributed over parallel machines. The processing time of any job is dependent on the usage of a scarce renewable resource, e.g., personnel. An amount of k units of that resource can be allocated to the jobs at any time, and the more of that resource is allocated to a job, the smaller its processing time. The dependence of processing times on the amount of resources is linear for any job. The objective is to find a resource allocation and a schedule that minimizes the makespan. Utilizing an integer quadratic programming relaxation, we show how to obtain a (3+e)-approximation algorithm for that problem, for any e>0. This generalizes and improves previous results, respectively. Our approach relies on a fully polynomial time approximation scheme to solve the quadratic programming relaxation. This result is interesting in itself, because the underlying quadratic program is NP-hard to solve in general. We also briefly discuss variants of the problem and derive lower bounds.

We develop the quantum theory of the spin light of neutrino ($SL\nu$) exactly accounting for the effect of background matter. Contrary to the already performed studies of the $SL\nu$, in this paper we derive explicit and closed expressions for the $SL\nu$ rate and power and for the emitted photon energy, which are valid for an arbitrary matter density (including very high values). The spatial distribution of the radiation power and the dependence of the emitted photon energy on the direction of radiation are also studied in detail for the first time. We analyze the $SL\nu$ polarization properties and show that within a wide range of neutrino momenta and matter densities the $SL\nu$ radiation is circularly polarized. Conditions for effective $SL\nu$ photon propagation in the electron plasma are discussed. It is also shown that in dense matter the average energy of the emitted photon can reach values in the range from one third of the neutrino momentum up to one half of the neutrino energy in matter. The main features of the studied radiation are summarized, and possibilities for the $SL\nu$ production during different astrophysical and cosmology processes are discussed., Comment: 15 pages, 7 figures, in: Proceedings of Les Recontres de Physique de la Vallee d'Aoste ("Results and Perspectives in Particle Physics", March 2005, La Thuile, Italy), ed. by Mario Greco, Frascati Physics Series, Italy, 2005; modified version is accepted for publication in Phys.Lett.B

This paper is concerned with polynomial time approximations schemes for the generalized geometric problems with geographic clustering. We illustrate the approach on the generalized traveling salesman problem which is also known as Group-TSP or TSP with neighborhoods. We prove that under the condition that all regions are non-intersecting and have comparable sizes and shapes, the problem admits PTAS. To derive a PTAS we extend the algorithm by Arora [2]. This extension involves the dissection mechanism and solution of the selection problem. We observe that the results are applicable to many generalized geometric problems, to other Minkowski norms, and to other ¯xed dimensional spaces.

This paper is concerned with a special case of the Generalized Minimum Spanning Tree Problem. The Generalized Minimum Spanning Tree Problem is de¯ned on an undirected graph, where the vertex set is partitioned into clusters, and non-negative costs are associated with the edges. The problem is to ¯nd a tree of minimum cost containing exactly one vertex in each cluster. We consider a geometric case of the problem where the graph is complete, all vertices are situated in the plane, and Euclidean distance de¯nes the edge cost. We prove that the problem admits PTAS if restricted to grid clustering.

We consider a Stackelberg pricing problem in directed networks:Tariffs (prices) have to be defined by an operator, the leader, for a subset of the arcs. Clients, the followers, choose paths to route their demand through the network selfishly and independently of each other, on the basis of minimal total cost. The problem is to find tariffs such as to maximize the operator''s revenue. We consider the case where each client takes at most one tariff arc to route the demand.The problem, which we refer to as the river tarification problem, is a special case of problems studied previously in the literature.We prove that the problem is strongly NP-hard.Moreover, we show that the polynomially solvable case of uniform tarification yields an m--approximation algorithm, and this is tight. We suggest a new type of analysis that allows to improve the result to \bigO{\log m}, whenever the input data is polynomially bounded. We furthermore derive an \bigO{m^{1-\varepsilon}}--inapproximability result for problems where the operator must serve all clients, and we discuss some polynomial special cases. Finally, a computational study with instances from France Telecom suggests that uniform pricing performs better in practice than theory would suggest.

Mixed model assembly systems assemble products (parts) of differenttypes in certain prespecified quantities. A minimal part set is a smallestpossible set of product type quantities, to be called the multiplicities,in which the numbers of assembled products of the various types are inthe desired ratios. It is common practice to repeatedly assemble minimalpart sets, and in such a way that the products of each of the minimalpart sets are assembled in the same sequence. Little is known howeverregarding the resulting throughput rate, in particular in comparison to thethroughput rates attainable by other input strategies. This paper investigatesthroughput and balancing issues in repetitive manufacturing environments.It considers sequencing problems that occur in this setting andhow the repetition strategy influences throughput. We model the problemsas a generalization of the traveling salesman problem and derive ourresults in this general setting. Our analysis uses well known concepts fromscheduling theory and combinatorial optimization.

We consider unrelated parallel machine scheduling problems with the objective to minimize the schedule makespan. In addition to its machine-dependence, the processing time of any job is also dependent on the usage of a scarce renewable resource. An amount of k units of that resource, e.g. workers, can be distributed over the jobs in process, and the more of that resource is allocated to a job, the smaller its processing time. The model generalizes the classical unrelated machine scheduling problem, adding a resource-time tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos, the difference lying in the fact the resource is renewable and not a total budget constraint. We use a two-phased LP rounding technique to assign resources to jobs and jobs to machines. Combined with Graham's list scheduling, we thus prove the existence of a $(4+2\sqrt{2})$-approximation algorithm. We show how our approach can be adapted to scheduling problems with dedicated machines as well, with an improvement of the performance bound to $(3+2\sqrt{2})$. Moreover, we derive a lower bound of 2 for the employed LP-based analysis, and we prove a (3/2)-inapproximability result.