Narrow Results

This paper studies the problem of dividing $m$ indivisible items among $n$ agents fairly and efficiently. Specifically, this research concentrates on pairwise maximin share (PMMS), which is defined to be the maximum value that an agent can guarantee for herself if she were to repartition the items with another agent and receive the bundle with the minimum value. PMMS is an important concept in the fair division. However, whether PMMS for indivisible items exists is still open. This work concentrates on PMMS by proving the existence of PMMS on linear graphs with binary valuation functions. Besides, this paper designs an algorithm to approximate PMMS in the case where different agents have identical valuations among the same items, achieving a ratio strictly greater than 0.8, which outperforms the state-of-the-art ratio of 0.781 from Kurokawa [22]. The time complexity of our FFD-based algorithm is $O(mn+mlogm)$.

MP systems are a class of P systems introduced for modeling metabolic processes. Here a regression method is presented for deducing a MP system exhibiting the dynamics of an observed metabolic system. In the procedure here described the knowledge of the stoichiometry of the system is combined with the log-gain principle of MP systems and is integrated with the Least Square Estimation method and with the stepwise regression approximation.

We discuss a number of essential questions concerning the state complexity research. The questions include why many basic problems were not studied earlier, whether there is a general algorithm for state complexity of combined operations, and whether there is a new and effective approach in this area of research. The concept of state complexity approximation is also discussed. We show that state complexity approximation can be used to obtain good results when the exact state complexities are difficult to find and when the exact state complexities are too complex to comprehend. We also list a number of questions for future research in this area.

In this paper, we study the two-dimensional geometrical bin packing problem (2DBP): given a list of rectangles, provide a packing of all these into the smallest possible number of unit bins without rotating the rectangles. Beyond its theoretical appeal, this problem has many practical applications, for example in print layout and VLSI chip design.

We present a 2-approximate algorithm, which improves over the previous best known ratio of 3, matches the best results for the problem where rotations are allowed and also matches the known lower bound of approximability. Our approach makes strong use of a PTAS for a related 2D knapsack problem and a new algorithm that can pack instances into two bins if OPT = 1.

We show how to train a weighted regular tree grammar such that it best approximates a weighted linear context-free tree grammar concerning the Kullback–Leibler divergence between both grammars. Furthermore, we construct a regular tree grammar that approximates the tree language induced by a context-free tree grammar.

We introduce and study a new Steiner tree problem variation called the bursty Steiner tree problem where new nodes arrive into bursts. This is an online problem which becomes the well-known online Steiner tree problem if the number of nodes in each burst is exactly one and becomes the classic Steiner tree problem if all the nodes appear in a single burst. In undirected graphs, we provide a tight bound of $\mathrm{\Theta }(\mathrm{\text{min}}\{logk,m\})$ on the competitive ratio for this problem, where $k$ is the total number of nodes to be connected and $m$ is the total number of different bursts. In directed graphs of bounded edge asymmetry $\alpha$, we provide a competitive ratio for this problem with a gap of ${𝒪}(\mathrm{\text{min}}\{\alpha ,m\})$ factor between the lower bound and the upper bound. We also show that a tight bound of $\mathrm{\Theta }(\mathrm{\text{min}}\{logk,m\})$ on the competitive ratio can be obtained for a bursty variation of the terminal Steiner tree problem. These are the first results that provide clear performance trade-offs for a novel Steiner tree problem variation that subsumes both of its online and classic versions.

We consider the problem of augmenting an $n$-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in $O(n{log}^{3}n)$ time, and (ii) the input graph is a tree, running in $O(n^{2}logn)$ time. We also present an algorithm for paths that computes a $(1+𝜀)$-approximation in $O(n+1/{𝜀}^3)$ time.

In our modern societies, a certain number of people do not own a car, by choice or by obligation. For some trips, there is no or few alternatives to the car. One way to make these trips possible for these people is to be transported by others who have already planned their trips. We propose to model this problem using as path-finding problem in a list edge-colored graph. This problem is a generalization of the $s-t$-path problem, studied by Böhmová et al. We consider two optimization functions: minimizing the number of color changes and minimizing the number of colors. We study for the previous problems, the classic complexity (polynomial-case, NP-completeness, hardness of approximation) and parameter complexity (W[2]-hardness) even in restricted cases. We also propose a lower bound for exact algorithm. On the positive side we provide a polynomial-time approximation algorithm and a FPT algorithm.

Let X be a compact metric space and A be a unital simple C*-algebra with TR(A)=0. Suppose that ϕ : C(X) → A is a unital monomorphism. We study the problem when ϕ can be approximated by homomorphisms with finite-dimensional range. We give a K-theoretical necessary and sufficient condition for ϕ being approximated by homomorphisms with finite-dimensional range.

In this paper, we study the approximation of negative plurisubharmonic functions with given boundary values. We want to approximate a plurisubharmonic function by an increasing sequence of plurisubharmonic functions defined on strictly larger domains.

Let π : Z → X be a holomorphic submersion of a complex manifold Z onto a complex manifold X and D ⋐ X a 1-convex domain with strongly pseudoconvex boundary. We prove that under certain conditions there always exists a spray of π-sections over which has prescribed core, it fixes the exceptional set E of D, and is dominating on . Each section in this spray is of class and holomorphic on D. As a consequence we obtain several approximation results for π-sections. In particular, we prove that π-sections which are of class and holomorphic on D can be approximated in the topology by π-sections that are holomorphic in open neighborhoods of . Under additional assumptions on the submersion we also get approximation by global holomorphic π-sections and the Oka principle over 1-convex manifolds. We include an application to the construction of proper holomorphic maps of 1-convex domains into q-convex manifolds.

In this paper, we present a coding method to capture QoS information in hypercube multicomputers. The coding method is based on a localized algorithm where each node interacts with its neighbors to gather QoS information. Specifically, each node maintains a QoS vector where the k-th element represents the guaranteed QoS performance to a destination that is k hops away. The localized algorithm exhibits desirable properties of self-stabilizing, self-optimizing, and self-healing. Simulation results show that this coding method provides a good approximation of the minimum QoS value to a k-hop destination and, at the same time, uses a relatively small number of packets to propagate a change in link state (QoS value) compared with the classical distributed Bellman-Ford method.

Dimension-adaptive sparse grid interpolation is a powerful tool to obtain surrogate functions of smooth, medium to high-dimensional objective models. In case of expensive models, the efficiency of the sparse grid algorithm is governed by the time required for the function evaluations. In this paper, we first briefly analyze the inherent parallelism of the standard dimension-adaptive algorithm. Then, we present an enhanced version of the standard algorithm that permits, in each step of the algorithm, a specified number (equal to the number of desired processes) of function evaluations to be executed in parallel, thereby increasing the parallel efficiency.

In this paper, we explore the problem of mapping linear chain applications onto large-scale heterogeneous platforms. A series of data sets enter the input stage and progress from stage to stage until the final result is computed. An important optimization criterion that should be considered in such a framework is the latency, or makespan, which measures the response time of the system in order to process one single data set entirely. For such applications, which are representative of a broad class of real-life applications, we can consider one-to-one mappings, in which each stage is mapped onto a single processor. However, in order to reduce the communication cost, it seems natural to group stages into intervals. The interval mapping problem can be solved in a straightforward way if the platform has homogeneous communications: the whole chain is grouped into a single interval, which in turn is mapped onto the fastest processor. But the problem becomes harder when considering a fully heterogeneous platform. Indeed, we prove the NP-completeness of this problem. Furthermore, we prove that neither the interval mapping problem nor the similar one-to-one mapping problem can be approximated in polynomial time by any constant factor (unless P=NP).

Ensuring different types of coverage is an important problem in many wireless sensor applications. In this paper, we address the problem of maintaining support coverage in the presence of sensor failures. Given a placement of n sensors in an area A, and any two points i and f in A, the support value of any path between i and f is the maximum distance of any point on the path from its closest sensor. The path with the minimum support value is called the maximal support path. The support value of a path may increase if a sensor fails. Given a maximal support path with a support value ψ, we first present two centralized approximation algorithms that, on failure of a single sensor, compute a new path with a support value close to ψ by moving exactly one nearby sensor. The first algorithm assumes that the sensors are allowed to move in any direction, and the second one assumes that the sensors are constrained to move in any of the four directions east, west, north, and south. Both the support value for the new path computed and the movement necessary are shown to be within a constant-factor of the initial support value. We then show that even in case of multiple sensor failures, a new path with a bounded support value can be computed. Detailed simulation results are provided to show that the algorithms result in significant improvement in many cases in practice, and the improvements obtained are significantly better than the worst case bounds given by the analysis. We also discuss distributed implementations of the algorithms.

We consider the PH/PH/c retrial queues with PH-retrial time. Approximation formulae for the distribution of the number of customers in service facility, sojourn time distribution and the mean number of customers in orbit are presented. We provide an approximation for GI/G/c retrial queue with general retrial time by approximating the general distribution with phase type distribution. Some numerical results are presented.

In this paper, we formulate a stochastic periodic-review inventory model with lead-time that considers both duration- and quantity-dependent inventory costs, and show that the optimality equation has the same format as the standard newsvendor problem with a modified demand distribution. We suggest (i) an approximation of the optimal order-up-to level, based on discretization of the inventory cost accounting, and (ii) two heuristic formulas, based on the two-moment normal approximation of the modified demand distribution, and on an approximated deterministic model. We evaluate the performances of these formulas using a Brownian motion demand process under different scenarios, and discuss their advantages and disadvantages.

We consider the problem of allocating a set of resources for performing a given collection of jobs. Each of the jobs has specific resource requirement for its execution. Each resource has specific start time, finish time and associated cost per unit usage. The objective is to execute the jobs while incurring minimum cost. The problem is NP-hard. We improve known four-approximation to a three-approximation algorithm. Our algorithm implies better approximation for two other related problems.

In this paper, we consider how to maximize the liquid welfare in a combinatorial auction where bidders have monotone valuations and are budget constrained. We study the setting that budgets are public information and present a universally truthful, budget feasible and computationally-efficient randomized $O(\sqrt{mn})$-approximate mechanism, where $m$ is the number of items and $n$ is the number of bidders, respectively.

The coefficients of new analytical forms for the deuteron wave function (DWF) in coordinate space for NijmI, NijmII, Nijm93, Reid93 and Argonne v18 potentials have been numerically calculated. The obtained wave functions do not contain any superfluous knots. The designed parameters of the deuteron are in good agreement with the experimental and theoretical data. The tensor polarization $t_{20}$ calculated based on the wave functions is proportionate to the earlier published results.