The Experts below are selected from a list of 54837 Experts worldwide ranked by ideXlab platform
Gianpiero Monaco - One of the best experts on this subject based on the ideXlab platform.
-
approximating the revenue Maximization Problem with sharp demands
Scandinavian Workshop on Algorithm Theory, 2014Co-Authors: Vittorio Bilo, Michele Flammini, Gianpiero MonacoAbstract:We consider the revenue Maximization Problem with sharp multi-demand, in which m indivisible items have to be sold to n potential buyers. Each buyer i is interested in getting exactly d i items, and each item j gives a benefit v ij to buyer i. We distinguish between unrelated and related valuations. In the former case, the benefit v ij is completely arbitrary, while, in the latter, each item j has a quality q j , each buyer i has a value v i and the benefit v ij is defined as the product v i q j . The Problem asks to determine a price for each item and an allocation of bundles of items to buyers with the aim of maximizing the total revenue, that is, the sum of the prices of all the sold items. The allocation must be envy-free, that is, each buyer must be happy with her assigned bundle and cannot improve her utility. We first prove that, for related valuations, the Problem cannot be approximated to a factor O(m 1 − e ), for any e > 0, unless P = NP and that such result is asymptotically tight. In fact we provide a simple m-approximation algorithm even for unrelated valuations. We then focus on an interesting subclass of “proper” instances, that do not contain buyers a priori known not being able to receive any item. For such instances, we design an interesting 2-approximation algorithm and show that no (2 − e)-approximation is possible for any 0 < e ≤ 1, unless P = NP. We observe that it is possible to efficiently check if an instance is proper, and if discarding useless buyers is allowed, an instance can be made proper in polynomial time, without worsening the value of its optimal solution.
-
approximating the revenue Maximization Problem with sharp demands
arXiv: Computer Science and Game Theory, 2013Co-Authors: Vittorio Bilo, Michele Flammini, Gianpiero MonacoAbstract:We consider the revenue Maximization Problem with sharp multi-demand, in which $m$ indivisible items have to be sold to $n$ potential buyers. Each buyer $i$ is interested in getting exactly $d_i$ items, and each item $j$ gives a benefit $v_{ij}$ to buyer $i$. We distinguish between unrelated and related valuations. In the former case, the benefit $v_{ij}$ is completely arbitrary, while, in the latter, each item $j$ has a quality $q_j$, each buyer $i$ has a value $v_i$ and the benefit $v_{ij}$ is defined as the product $v_i q_j$. The Problem asks to determine a price for each item and an allocation of bundles of items to buyers with the aim of maximizing the total revenue, that is, the sum of the prices of all the sold items. The allocation must be envy-free, that is, each buyer must be happy with her assigned bundle and cannot improve her utility. We first prove that, for related valuations, the Problem cannot be approximated to a factor $O(m^{1-\epsilon})$, for any $\epsilon>0$, unless {\sf P} = {\sf NP} and that such result is asymptotically tight. In fact we provide a simple $m$-approximation algorithm even for unrelated valuations. We then focus on an interesting subclass of "proper" instances, that do not contain buyers a priori known not being able to receive any item. For such instances, we design an interesting $2$-approximation algorithm and show that no $(2-\epsilon)$-approximation is possible for any $0<\epsilon\leq 1$, unless {\sf P} $=$ {\sf NP}. We observe that it is possible to efficiently check if an instance is proper, and if discarding useless buyers is allowed, an instance can be made proper in polynomial time, without worsening the value of its optimal solution.
Vittorio Bilo - One of the best experts on this subject based on the ideXlab platform.
-
approximating the revenue Maximization Problem with sharp demands
Scandinavian Workshop on Algorithm Theory, 2014Co-Authors: Vittorio Bilo, Michele Flammini, Gianpiero MonacoAbstract:We consider the revenue Maximization Problem with sharp multi-demand, in which m indivisible items have to be sold to n potential buyers. Each buyer i is interested in getting exactly d i items, and each item j gives a benefit v ij to buyer i. We distinguish between unrelated and related valuations. In the former case, the benefit v ij is completely arbitrary, while, in the latter, each item j has a quality q j , each buyer i has a value v i and the benefit v ij is defined as the product v i q j . The Problem asks to determine a price for each item and an allocation of bundles of items to buyers with the aim of maximizing the total revenue, that is, the sum of the prices of all the sold items. The allocation must be envy-free, that is, each buyer must be happy with her assigned bundle and cannot improve her utility. We first prove that, for related valuations, the Problem cannot be approximated to a factor O(m 1 − e ), for any e > 0, unless P = NP and that such result is asymptotically tight. In fact we provide a simple m-approximation algorithm even for unrelated valuations. We then focus on an interesting subclass of “proper” instances, that do not contain buyers a priori known not being able to receive any item. For such instances, we design an interesting 2-approximation algorithm and show that no (2 − e)-approximation is possible for any 0 < e ≤ 1, unless P = NP. We observe that it is possible to efficiently check if an instance is proper, and if discarding useless buyers is allowed, an instance can be made proper in polynomial time, without worsening the value of its optimal solution.
-
approximating the revenue Maximization Problem with sharp demands
arXiv: Computer Science and Game Theory, 2013Co-Authors: Vittorio Bilo, Michele Flammini, Gianpiero MonacoAbstract:We consider the revenue Maximization Problem with sharp multi-demand, in which $m$ indivisible items have to be sold to $n$ potential buyers. Each buyer $i$ is interested in getting exactly $d_i$ items, and each item $j$ gives a benefit $v_{ij}$ to buyer $i$. We distinguish between unrelated and related valuations. In the former case, the benefit $v_{ij}$ is completely arbitrary, while, in the latter, each item $j$ has a quality $q_j$, each buyer $i$ has a value $v_i$ and the benefit $v_{ij}$ is defined as the product $v_i q_j$. The Problem asks to determine a price for each item and an allocation of bundles of items to buyers with the aim of maximizing the total revenue, that is, the sum of the prices of all the sold items. The allocation must be envy-free, that is, each buyer must be happy with her assigned bundle and cannot improve her utility. We first prove that, for related valuations, the Problem cannot be approximated to a factor $O(m^{1-\epsilon})$, for any $\epsilon>0$, unless {\sf P} = {\sf NP} and that such result is asymptotically tight. In fact we provide a simple $m$-approximation algorithm even for unrelated valuations. We then focus on an interesting subclass of "proper" instances, that do not contain buyers a priori known not being able to receive any item. For such instances, we design an interesting $2$-approximation algorithm and show that no $(2-\epsilon)$-approximation is possible for any $0<\epsilon\leq 1$, unless {\sf P} $=$ {\sf NP}. We observe that it is possible to efficiently check if an instance is proper, and if discarding useless buyers is allowed, an instance can be made proper in polynomial time, without worsening the value of its optimal solution.
Michele Flammini - One of the best experts on this subject based on the ideXlab platform.
-
approximating the revenue Maximization Problem with sharp demands
Scandinavian Workshop on Algorithm Theory, 2014Co-Authors: Vittorio Bilo, Michele Flammini, Gianpiero MonacoAbstract:We consider the revenue Maximization Problem with sharp multi-demand, in which m indivisible items have to be sold to n potential buyers. Each buyer i is interested in getting exactly d i items, and each item j gives a benefit v ij to buyer i. We distinguish between unrelated and related valuations. In the former case, the benefit v ij is completely arbitrary, while, in the latter, each item j has a quality q j , each buyer i has a value v i and the benefit v ij is defined as the product v i q j . The Problem asks to determine a price for each item and an allocation of bundles of items to buyers with the aim of maximizing the total revenue, that is, the sum of the prices of all the sold items. The allocation must be envy-free, that is, each buyer must be happy with her assigned bundle and cannot improve her utility. We first prove that, for related valuations, the Problem cannot be approximated to a factor O(m 1 − e ), for any e > 0, unless P = NP and that such result is asymptotically tight. In fact we provide a simple m-approximation algorithm even for unrelated valuations. We then focus on an interesting subclass of “proper” instances, that do not contain buyers a priori known not being able to receive any item. For such instances, we design an interesting 2-approximation algorithm and show that no (2 − e)-approximation is possible for any 0 < e ≤ 1, unless P = NP. We observe that it is possible to efficiently check if an instance is proper, and if discarding useless buyers is allowed, an instance can be made proper in polynomial time, without worsening the value of its optimal solution.
-
approximating the revenue Maximization Problem with sharp demands
arXiv: Computer Science and Game Theory, 2013Co-Authors: Vittorio Bilo, Michele Flammini, Gianpiero MonacoAbstract:We consider the revenue Maximization Problem with sharp multi-demand, in which $m$ indivisible items have to be sold to $n$ potential buyers. Each buyer $i$ is interested in getting exactly $d_i$ items, and each item $j$ gives a benefit $v_{ij}$ to buyer $i$. We distinguish between unrelated and related valuations. In the former case, the benefit $v_{ij}$ is completely arbitrary, while, in the latter, each item $j$ has a quality $q_j$, each buyer $i$ has a value $v_i$ and the benefit $v_{ij}$ is defined as the product $v_i q_j$. The Problem asks to determine a price for each item and an allocation of bundles of items to buyers with the aim of maximizing the total revenue, that is, the sum of the prices of all the sold items. The allocation must be envy-free, that is, each buyer must be happy with her assigned bundle and cannot improve her utility. We first prove that, for related valuations, the Problem cannot be approximated to a factor $O(m^{1-\epsilon})$, for any $\epsilon>0$, unless {\sf P} = {\sf NP} and that such result is asymptotically tight. In fact we provide a simple $m$-approximation algorithm even for unrelated valuations. We then focus on an interesting subclass of "proper" instances, that do not contain buyers a priori known not being able to receive any item. For such instances, we design an interesting $2$-approximation algorithm and show that no $(2-\epsilon)$-approximation is possible for any $0<\epsilon\leq 1$, unless {\sf P} $=$ {\sf NP}. We observe that it is possible to efficiently check if an instance is proper, and if discarding useless buyers is allowed, an instance can be made proper in polynomial time, without worsening the value of its optimal solution.
Mourad Lazgham - One of the best experts on this subject based on the ideXlab platform.
-
Regularity properties in a state-constrained expected utility Maximization Problem
Mathematical Methods of Operations Research, 2018Co-Authors: Mourad LazghamAbstract:We consider a stochastic optimal control Problem in a market model with temporary and permanent price impact, which is related to an expected utility Maximization Problem under finite fuel constraint. We establish the initial condition fulfilled by the corresponding value function and show its first regularity property. Moreover, we can prove the existence and uniqueness of an optimal strategy under rather mild model assumptions. This will then allow us to derive further regularity properties of the corresponding value function, in particular its continuity and partial differentiability. As a consequence of the continuity of the value function, we will prove a dynamic programming principle without appealing to the classical measurable selection arguments. This permits us to establish a tight relation between our value function and a nonlinear parabolic degenerated Hamilton–Jacobi–Bellman (HJB) equation with singularity . To conclude, we show a comparison principle, which allows us to characterize our value function as the unique viscosity solution of the HJB equation.
-
regularity properties in a state constrained expected utility Maximization Problem
Research Papers in Economics, 2015Co-Authors: Mourad LazghamAbstract:We consider a stochastic optimal control Problem in a market model with temporary and permanent price impact, which is related to an expected utility Maximization Problem under finite fuel constraint. We establish the initial condition fulfilled by the corresponding value function and show its first regularity property. Moreover, we can prove the existence and uniqueness of optimal strategies under rather mild model assumptions. On the one hand, this result is of independent interest. On the other hand, it will then allow us to derive further regularity properties of the corresponding value function, in particular its continuity and partial differentiability. As a consequence of the continuity of the value function, we will prove the dynamic programming principle without appealing to the classical measurable selection arguments.
Hayk Mikayelyan - One of the best experts on this subject based on the ideXlab platform.
-
Fractional optimal Maximization Problem and the unstable fractional obstacle Problem
Journal of Mathematical Analysis and Applications, 2021Co-Authors: Julián Fernández Bonder, Zhiwei Cheng, Hayk MikayelyanAbstract:Abstract We consider an optimal rearrangement Maximization Problem involving the fractional Laplace operator ( − Δ ) s , 0 s 1 , and the Gagliardo-Nirenberg seminorm [ u ] s . We prove the existence of a maximizer, analyze its properties and show that it satisfies the unstable fractional obstacle Problem equation for some α > 0 ( − Δ ) s u = χ { u > α } .
-
Fractional optimal Maximization Problem and the unstable fractional obstacle Problem
arXiv: Analysis of PDEs, 2019Co-Authors: Julián Fernández Bonder, Zhiwei Cheng, Hayk MikayelyanAbstract:We consider an optimal rearrangement Maximization Problem involving the fractional Laplace operator $(-\Delta)^s$, $0 0$ $$(-\Delta)^s u=\chi_{\{u>\alpha\}}.$$
