-
Dual Bounded Generation: Polynomial, Second-order Cone and Positive Semidefinite Matrix Inequalities
Authors:
Khaled Elbassioni
Abstract:
In the monotone integer dualization problem, we are given two sets of vectors in an integer box such that no vector in the first set is dominated by a vector in the second. The question is to check if the two sets of vectors cover the entire integer box by upward and downward domination, respectively. It is known that the problem is (quasi-)polynomially equivalent to that of enumerating all maxima…
▽ More
In the monotone integer dualization problem, we are given two sets of vectors in an integer box such that no vector in the first set is dominated by a vector in the second. The question is to check if the two sets of vectors cover the entire integer box by upward and downward domination, respectively. It is known that the problem is (quasi-)polynomially equivalent to that of enumerating all maximal feasible solutions of a given monotone system of linear/separable/supermodular inequalities over integer vectors. The equivalence is established via showing that the dual family of minimal infeasible vectors has size bounded by a (quasi-)polynomial in the sizes of the family to be generated and the input description. Continuing in this line of work, in this paper, we consider systems of polynomial, second-order cone, and semidefinite inequalities. We give sufficient conditions under which such bounds can be established and highlight some applications.
△ Less
Submitted 2 July, 2024;
originally announced July 2024.
-
Improved Approximation Guarantees for Power Scheduling Problems With Sum-of-Squares Constraints
Authors:
Trung Thanh Nguyen,
Khaled Elbassioni,
Areg Karapetyan,
Majid Khonji
Abstract:
We study a class of combinatorial scheduling problems characterized by a particular type of constraint often associated with electrical power or gas energy. This constraint appears in several practical applications and is expressed as a sum of squares of linear functions. Its nonlinear nature adds complexity to the scheduling problem, rendering it notably challenging, even in the case of a linear…
▽ More
We study a class of combinatorial scheduling problems characterized by a particular type of constraint often associated with electrical power or gas energy. This constraint appears in several practical applications and is expressed as a sum of squares of linear functions. Its nonlinear nature adds complexity to the scheduling problem, rendering it notably challenging, even in the case of a linear objective. In fact, exact polynomial time algorithms are unlikely to exist, and thus, prior works have focused on designing approximation algorithms with polynomial running time and provable guarantees on the solution quality. In an effort to advance this line of research, we present novel approximation algorithms yielding significant improvements over the existing state-of-the-art results for these problems.
△ Less
Submitted 24 December, 2023;
originally announced December 2023.
-
DClEVerNet: Deep Combinatorial Learning for Efficient EV Charging Scheduling in Large-scale Networked Facilities
Authors:
Bushra Alshehhi,
Areg Karapetyan,
Khaled Elbassioni,
Sid Chi-Kin Chau,
Majid Khonji
Abstract:
With the electrification of transportation, the rising uptake of electric vehicles (EVs) might stress distribution networks significantly, leaving their performance degraded and stability jeopardized. To accommodate these new loads cost-effectively, modern power grids require coordinated or ``smart'' charging strategies capable of optimizing EV charging scheduling in a scalable and efficient fashi…
▽ More
With the electrification of transportation, the rising uptake of electric vehicles (EVs) might stress distribution networks significantly, leaving their performance degraded and stability jeopardized. To accommodate these new loads cost-effectively, modern power grids require coordinated or ``smart'' charging strategies capable of optimizing EV charging scheduling in a scalable and efficient fashion. With this in view, the present work focuses on reservation management programs for large-scale, networked EV charging stations. We formulate a time-coupled binary optimization problem that maximizes EV users' total welfare gain while accounting for the network's available power capacity and stations' occupancy limits. To tackle the problem at scale while retaining high solution quality, a data-driven optimization framework combining techniques from the fields of Deep Learning and Approximation Algorithms is introduced. The framework's key ingredient is a novel input-output processing scheme for neural networks that allows direct extrapolation to problem sizes substantially larger than those included in the training set. Extensive numerical simulations based on synthetic and real-world data traces verify the effectiveness and superiority of the presented approach over two representative scheduling algorithms. Lastly, we round up the contributions by listing several immediate extensions to the proposed framework and outlining the prospects for further exploration.
△ Less
Submitted 22 August, 2023; v1 submitted 18 May, 2023;
originally announced May 2023.
-
Joint Rate Allocation and Power Control for RSMA-Based Communication and Radar Coexistence Systems
Authors:
Trung Thanh Nguyen,
Nguyen Cong Luong,
Shaohan Feng,
Tien Hoa Nguyen,
Khaled Elbassioni,
Dusit Niyato,
Dong In Kim
Abstract:
We consider a rate-splitting multiple access (RSMA)-based communication and radar coexistence (CRC) system. The proposed system allows an RSMA-based communication system to share spectrum with multiple radars. Furthermore, RSMA enables flexible and powerful interference management by splitting messages into common parts and private parts to partially decode interference and partially treat interfe…
▽ More
We consider a rate-splitting multiple access (RSMA)-based communication and radar coexistence (CRC) system. The proposed system allows an RSMA-based communication system to share spectrum with multiple radars. Furthermore, RSMA enables flexible and powerful interference management by splitting messages into common parts and private parts to partially decode interference and partially treat interference as noise. The RSMA-based CRC system thus significantly improves spectral efficiency, energy efficiency and quality of service (QoS) of communication users (CUs). However, the RSMA-based CRC system raises new challenges. Due to the spectrum sharing, the communication network and the radars cause interference to each other, which reduces the signal-to-interference-plus-noise ratio (SINR) of the radars as well as the data rate of the CUs in the communication network. Therefore, a major problem is to maximize the sum rate of the CUs while guaranteeing their QoS requirements of data transmissions and the SINR requirements of multiple radars. To achieve these objectives, we formulate a problem that optimizes i) the common rate allocation to the CUs, transmit power of common messages and transmit power of private messages of the CUs, and ii) transmit power of the radars. The problem is non-convex with multiple decision parameters, which is challenging to be solved. We propose two algorithms. The first sequential quadratic programming (SQP) can quickly return a local optimal solution, and has been known to be the state-of-the-art in nonlinear programming methods. The second is an additive approximation scheme (AAS) which solves the problem globally in a reasonable amount of time, based on the technique of applying exhaustive enumeration to a modified instance. The simulation results show the improvement of the AAS compared with the SQP in terms of sum rate.
△ Less
Submitted 30 March, 2023;
originally announced March 2023.
-
Informational Rescaling of PCA Maps with Application to Genetic Distance
Authors:
Nassim Nicholas Taleb,
Pierre Zalloua,
Khaled Elbassioni,
Andreas Henschel,
Daniel E. Platt
Abstract:
We discuss the inadequacy of covariances/correlations and other measures in L2 as relative distance metrics under some conditions. We propose a computationally simple heuristic to transform a map based on standard principal component analysis (PCA) (when the variables are asymptotically Gaussian) into an entropy-based map where distances are based on mutual information (MI). Rescaling Principal Co…
▽ More
We discuss the inadequacy of covariances/correlations and other measures in L2 as relative distance metrics under some conditions. We propose a computationally simple heuristic to transform a map based on standard principal component analysis (PCA) (when the variables are asymptotically Gaussian) into an entropy-based map where distances are based on mutual information (MI). Rescaling Principal Component based distances using MI allows a representation of relative statistical associations when, as in genetics, it is applied on bit measurements between individuals' genomic mutual information.
This entropy rescaled PCA, while preserving order relationships (along a dimension), changes the relative distances to make them linear to information. We show the effect on the entire world population and some subsamples, which leads to significant differences with the results of current research.
△ Less
Submitted 4 March, 2024; v1 submitted 14 March, 2023;
originally announced March 2023.
-
Access Management in Joint Sensing and Communication Systems: Efficiency versus Fairness
Authors:
Trung Thanh Nguyen,
Khaled Elbassioni,
Nguyen Cong Luong,
Dusit Niyato,
Dong In Kim
Abstract:
In this paper, we consider a distributed joint sensing and communication (DJSC) system in which multiple radar sensors are deployed. Each sensor is equipped with a sensing function and a communication function, and thus it is a JSC node. The JSC nodes are able to perform sensing their surrounding environments, e.g., weather conditions or available spectrum. Furthermore, they can cooperatively dete…
▽ More
In this paper, we consider a distributed joint sensing and communication (DJSC) system in which multiple radar sensors are deployed. Each sensor is equipped with a sensing function and a communication function, and thus it is a JSC node. The JSC nodes are able to perform sensing their surrounding environments, e.g., weather conditions or available spectrum. Furthermore, they can cooperatively detect and track a common target. The information, i.e., of the environment and target, collected by the JSC nodes is transmitted to a base station (BS) for further processing. As such, different aspects of the target to be viewed simultaneously, which significantly improves the performance of the target detection and tracking. However, both the sensing function and communication function require a certain amount of bandwidth for their operations, and deploying multiple JSC nodes may consume a large amount of bandwidth. Therefore, we investigate the bandwidth allocation problem for the DJSC system. In particular, we aim to optimize the bandwidth allocation to the sensing function and the communication function of the JSC nodes. To improve the allocation efficiency while benefiting the spatial diversity advantage of the DJSC systems, the objective is to maximize the sum of sensing performances, i.e., estimation rates, communication performances, i.e., communication data rates, and fairnesses of all the users. The optimization problem is non-convex and difficult to be solved. For this, we propose a fully polynomial time approximation algorithm, and we prove that the approximation algorithm can guarantee a near-optimal solution with an accuracy bound of $ε$. Furthermore, we propose to use a heuristic algorithm with lower complexity. The simulation results show that both the proposed algorithms are able to achieve the solutions close to the optimum in a computationally efficient fashion.
△ Less
Submitted 7 November, 2021;
originally announced November 2021.
-
Anti Tai Mapping for Unordered Labeled Trees
Authors:
Mislav Blažević,
Stefan Canzar,
Khaled Elbassioni,
Domagoj Matijević
Abstract:
The well-studied Tai mapping between two rooted labeled trees $T_1(V_1, E_1)$ and $T_2(V_2, E_2)$ defines a one-to-one mapping between nodes in $T_1$ and $T_2$ that preserves ancestor relationship. For unordered trees the problem of finding a maximum-weight Tai mapping is known to be NP-complete. In this work, we define an anti Tai mapping $M\subseteq V_1\times V_2$ as a binary relation between tw…
▽ More
The well-studied Tai mapping between two rooted labeled trees $T_1(V_1, E_1)$ and $T_2(V_2, E_2)$ defines a one-to-one mapping between nodes in $T_1$ and $T_2$ that preserves ancestor relationship. For unordered trees the problem of finding a maximum-weight Tai mapping is known to be NP-complete. In this work, we define an anti Tai mapping $M\subseteq V_1\times V_2$ as a binary relation between two unordered labeled trees such that any two $(x,y), (x', y')\in M$ violate ancestor relationship and thus cannot be part of the same Tai mapping, i.e. $(x\le x' \iff y\not \le y') \vee (x'\le x \iff y'\not \le y)$, given an ancestor order $x<x'$ meaning that $x$ is an ancestor of $x'$. Finding a maximum-weight anti Tai mapping arises in the cutting plane method for solving the maximum-weight Tai mapping problem via integer programming. We give an efficient polynomial-time algorithm for finding a maximum-weight anti Tai mapping for the case when one of the two trees is a path and further show how to extend this result in order to provide a polynomially computable lower bound on the optimal anti Tai mapping for two unordered labeled trees. The latter result stems from the special class of anti Tai mapping defined by the more restricted condition $x\sim x' \iff y\not\sim y'$, where $\sim$ denotes that two nodes belong to the same root-to-leaf path. For this class, we give an efficient algorithm that solves the problem directly on two unordered trees in $O(|V_1|^2|V_2|^2)$.
△ Less
Submitted 17 July, 2021;
originally announced July 2021.
-
Threshold Rounding for the Standard LP Relaxation of some Geometric Stabbing Problems
Authors:
Khaled Elbassioni,
Saurabh Ray
Abstract:
In the rectangle stabbing problem, we are given a set $\cR$ of axis-aligned rectangles in $\RR^2$, and the objective is to find a minimum-cardinality set of horizontal and/or vertical lines such that each rectangle is intersected by one of these lines. The standard LP relaxation for this problem is known to have an integrality gap of 2, while a better intergality gap of 1.58.. is known for the spe…
▽ More
In the rectangle stabbing problem, we are given a set $\cR$ of axis-aligned rectangles in $\RR^2$, and the objective is to find a minimum-cardinality set of horizontal and/or vertical lines such that each rectangle is intersected by one of these lines. The standard LP relaxation for this problem is known to have an integrality gap of 2, while a better intergality gap of 1.58.. is known for the special case when $\cR$ is a set of horizontal segments. In this paper, we consider two more special cases: when $\cR$ is a set of horizontal and vertical segments, and when $\cR$ is a set of unit squares. We show that the integrality gap of the standard LP relaxation in both cases is stricly less than $2$. Our rounding technique is based on a generalization of the {\it threshold rounding} idea used by Kovaleva and Spieksma (SIAM J. Disc. Math 2006), which may prove useful for rounding the LP relaxations of other geometric covering problems.
△ Less
Submitted 23 June, 2021;
originally announced June 2021.
-
Approximately Socially-Optimal Decentralized Coalition Formation with Application to P2P Energy Sharing
Authors:
Sid Chi-Kin Chau,
Khaled Elbassioni,
Yue Zhou
Abstract:
The paradigm of P2P (peer-to-peer) economy has emerged in diverse areas. "P2P energy sharing" is a new form of P2P economy in the energy sector, which allows users to establish longer-term sharing arrangements of their local energy resources (e.g., rooftop PVs, home batteries) with joint optimized energy management. In such a P2P setting, a coalition of users is formed for sharing resources in a d…
▽ More
The paradigm of P2P (peer-to-peer) economy has emerged in diverse areas. "P2P energy sharing" is a new form of P2P economy in the energy sector, which allows users to establish longer-term sharing arrangements of their local energy resources (e.g., rooftop PVs, home batteries) with joint optimized energy management. In such a P2P setting, a coalition of users is formed for sharing resources in a decentralized manner by self-interested users based on their individual preferences. A likely outcome of decentralized coalition formation will be a stable coalition structure, where no group of users could cooperatively opt out to form another coalition that induces higher preferences to all its members. Remarkably, there exist a number of fair cost-sharing mechanisms (e.g., equal-split, proportional-split, egalitarian and Nash bargaining solutions of bargaining games) that model practical cost-sharing applications with desirable properties, such as the existence of a stable coalition structure with a small strong price-of-anarchy (SPoA) to approximate the social optimum. In this paper, we provide general results of decentralized coalition formation: (1) We establish a logarithmic lower bound on SPoA, and hence, show several previously known fair cost-sharing mechanisms are the best practical mechanisms with minimal SPoA. (2) We show that the SPoA of egalitarian and Nash bargaining cost-sharing mechanisms to match the lower bound. (3) We derive the SPoA of a mix of different cost-sharing mechanisms. (4) We present a decentralized algorithm to form a stable coalition structure. (5) Finally, we apply our general results to P2P energy sharing and present an empirical study of decentralized coalition formation in a real-world project. We study the empirical SPoA, which is observed within 95% of the social optimal cost with coalitions of 2 and 3 users, via fair cost-sharing mechanisms.
△ Less
Submitted 5 October, 2022; v1 submitted 18 September, 2020;
originally announced September 2020.
-
On Dualization over Distributive Lattices
Authors:
Khaled Elbassioni
Abstract:
Given a partially order set (poset) $P$, and a pair of families of ideals $\mathcal{I}$ and filters $\mathcal{F}$ in $P$ such that each pair $(I,F)\in \mathcal{I}\times\mathcal{F}$ has a non-empty intersection, the dualization problem over $P$ is to check whether there is an ideal $X$ in $P$ which intersects every member of $\mathcal{F}$ and does not contain any member of $\mathcal{I}$. Equivalent…
▽ More
Given a partially order set (poset) $P$, and a pair of families of ideals $\mathcal{I}$ and filters $\mathcal{F}$ in $P$ such that each pair $(I,F)\in \mathcal{I}\times\mathcal{F}$ has a non-empty intersection, the dualization problem over $P$ is to check whether there is an ideal $X$ in $P$ which intersects every member of $\mathcal{F}$ and does not contain any member of $\mathcal{I}$. Equivalently, the problem is to check for a distributive lattice $L=L(P)$, given by the poset $P$ of its set of joint-irreducibles, and two given antichains $\mathcal{A},\mathcal{B}\subseteq L$ such that no $a\in\mathcal{A}$ is dominated by any $b\in\mathcal{B}$, whether $\mathcal{A}$ and $\mathcal{B}$ cover (by domination) the entire lattice. We show that the problem can be solved in quasi-polynomial time in the sizes of $P$, $\mathcal{A}$ and $\mathcal{B}$, thus answering an open question in Babin and Kuznetsov (2017). As an application, we show that minimal infrequent closed sets of attributes in a rational database, with respect to a given implication base of maximum premise size of one, can be enumerated in incremental quasi-polynomial time.
△ Less
Submitted 21 October, 2022; v1 submitted 27 June, 2020;
originally announced June 2020.
-
Generating clause sequences of a CNF formula
Authors:
Kristóf Bérczi,
Endre Boros,
Ondřej Čepek,
Khaled Elbassioni,
Petr Kučera,
Kazuhisa Makino
Abstract:
Given a CNF formula $Φ$ with clauses $C_1,\ldots,C_m$ and variables $V=\{x_1,\ldots,x_n\}$, a truth assignment $a:V\rightarrow\{0,1\}$ of $Φ$ leads to a clause sequence $σ_Φ(a)=(C_1(a),\ldots,C_m(a))\in\{0,1\}^m$ where $C_i(a) = 1$ if clause $C_i$ evaluates to $1$ under assignment $a$, otherwise $C_i(a) = 0$. The set of all possible clause sequences carries a lot of information on the formula, e.g…
▽ More
Given a CNF formula $Φ$ with clauses $C_1,\ldots,C_m$ and variables $V=\{x_1,\ldots,x_n\}$, a truth assignment $a:V\rightarrow\{0,1\}$ of $Φ$ leads to a clause sequence $σ_Φ(a)=(C_1(a),\ldots,C_m(a))\in\{0,1\}^m$ where $C_i(a) = 1$ if clause $C_i$ evaluates to $1$ under assignment $a$, otherwise $C_i(a) = 0$. The set of all possible clause sequences carries a lot of information on the formula, e.g. SAT, MAX-SAT and MIN-SAT can be encoded in terms of finding a clause sequence with extremal properties.
We consider a problem posed at Dagstuhl Seminar 19211 "Enumeration in Data Management" (2019) about the generation of all possible clause sequences of a given CNF with bounded dimension. We prove that the problem can be solved in incremental polynomial time. We further give an algorithm with polynomial delay for the class of tractable CNF formulas. We also consider the generation of maximal and minimal clause sequences, and show that generating maximal clause sequences is NP-hard, while minimal clause sequences can be generated with polynomial delay.
△ Less
Submitted 16 February, 2020;
originally announced February 2020.
-
Some Black-box Reductions for Objective-robust Discrete Optimization Problems Based on their LP-Relaxations
Authors:
Khaled Elbassioni
Abstract:
We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. We show how an integrality gap verifier for the linear programming relaxation of the non-robust version of the problem can be used to derive approximation algorithms for the robust version.
We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. We show how an integrality gap verifier for the linear programming relaxation of the non-robust version of the problem can be used to derive approximation algorithms for the robust version.
△ Less
Submitted 15 July, 2019;
originally announced July 2019.
-
Quasi-polynomial Algorithms for List-coloring of Nearly Intersecting Hypergraphs
Authors:
Khaled Elbassioni
Abstract:
A hypergraph $\mathcal{H}$ on $n$ vertices and $m$ edges is said to be {\it nearly-intersecting} if every edge of $\mathcal{H}$ intersects all but at most polylogarthmically many (in $m$ and $n$) other edges. Given lists of colors $\mathcal{L}(v)$, for each vertex $v\in V$, $\mathcal{H}$ is said to be $\mathcal{L}$-(list) colorable, if each vertex can be assigned a color from its list such that no…
▽ More
A hypergraph $\mathcal{H}$ on $n$ vertices and $m$ edges is said to be {\it nearly-intersecting} if every edge of $\mathcal{H}$ intersects all but at most polylogarthmically many (in $m$ and $n$) other edges. Given lists of colors $\mathcal{L}(v)$, for each vertex $v\in V$, $\mathcal{H}$ is said to be $\mathcal{L}$-(list) colorable, if each vertex can be assigned a color from its list such that no edge in $\mathcal{H}$ is monochromatic. We show that list-colorability for any nearly intersecting hypergraph, and lists drawn from a set of constant size, can be checked in quasi-polynomial time in $m$ and $n$.
△ Less
Submitted 4 April, 2019;
originally announced April 2019.
-
Price of Anarchy in Algorithmic Matching of Romantic Partners
Authors:
Andrés Abeliuk,
Khaled Elbassioni,
Talal Rahwan,
Manuel Cebrian,
Iyad Rahwan
Abstract:
Algorithmic-matching sites offer users access to an unprecedented number of potential mates. However, they also pose a principal-agent problem with a potential moral hazard. The agent's interest is to maximize usage of the Web site, while the principal's interest is to find the best possible romantic partners. This creates a conflict of interest: optimally matching users would lead to stable coupl…
▽ More
Algorithmic-matching sites offer users access to an unprecedented number of potential mates. However, they also pose a principal-agent problem with a potential moral hazard. The agent's interest is to maximize usage of the Web site, while the principal's interest is to find the best possible romantic partners. This creates a conflict of interest: optimally matching users would lead to stable couples and fewer singles using the site, which is detrimental for the online dating industry. Here, we borrow the notion of Price-of-Anarchy from game theory to quantify the decrease in social efficiency of online dating sites caused by the agent's self-interest. We derive theoretical bounds on the price-of-anarchy, showing it can be bounded by a constant that does not depend on the number of users of the dating site. This suggests that as online dating sites grow, their potential benefits scale up without sacrificing social efficiency. Further, we performed experiments involving human subjects in a matching market, and compared the social welfare achieved by an optimal matching service against a self-interest matching algorithm. We show that by introducing competition among dating sites, the selfish behavior of agents aligns with its users, and social efficiency increases.
△ Less
Submitted 15 February, 2019; v1 submitted 8 January, 2019;
originally announced January 2019.
-
Finding Sparse Solutions for Packing and Covering Semidefinite Programs
Authors:
Khaled Elbassioni,
Kazuhisa Makino
Abstract:
Packing and covering semidefinite programs (SDPs) appear in natural relaxations of many combinatorial optimization problems as well as a number of other applications. Recently, several techniques were proposed, that utilize the particular structure of this class of problems, to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, such as those descr…
▽ More
Packing and covering semidefinite programs (SDPs) appear in natural relaxations of many combinatorial optimization problems as well as a number of other applications. Recently, several techniques were proposed, that utilize the particular structure of this class of problems, to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, such as those described in this paper, it may be desirable to obtain {\it sparse} dual solutions, i.e., those with support size (almost) independent of the number of primal constraints. In this paper, we give an algorithm that finds such solutions, which is an extension of a {\it logarithmic-potential} based algorithm of Grigoriadis, Khachiyan, Porkolab and Villavicencio (SIAM Journal of Optimization 41 (2001)) for packing/covering linear programs.
△ Less
Submitted 15 February, 2019; v1 submitted 25 September, 2018;
originally announced September 2018.
-
Computational Aspects of Optimal Strategic Network Diffusion
Authors:
Marcin Waniek,
Khaled Elbassioni,
Flavio L. Pinheiro,
Cesar A. Hidalgo,
Aamena Alshamsi
Abstract:
Diffusion on complex networks is often modeled as a stochastic process. Yet, recent work on strategic diffusion emphasizes the decision power of agents and treats diffusion as a strategic problem. Here we study the computational aspects of strategic diffusion, i.e., finding the optimal sequence of nodes to activate a network in the minimum time. We prove that finding an optimal solution to this pr…
▽ More
Diffusion on complex networks is often modeled as a stochastic process. Yet, recent work on strategic diffusion emphasizes the decision power of agents and treats diffusion as a strategic problem. Here we study the computational aspects of strategic diffusion, i.e., finding the optimal sequence of nodes to activate a network in the minimum time. We prove that finding an optimal solution to this problem is NP-complete in a general case. To overcome this computational difficulty, we present an algorithm to compute an optimal solution based on a dynamic programming technique. We also show that the problem is fixed parameter-tractable when parametrized by the product of the treewidth and maximum degree. We analyze the possibility of developing an efficient approximation algorithm and show that two heuristic algorithms proposed so far cannot have better than a logarithmic approximation guarantee. Finally, we prove that the problem does not admit better than a logarithmic approximation, unless P=NP.
△ Less
Submitted 30 January, 2020; v1 submitted 10 September, 2018;
originally announced September 2018.
-
Approximations for Generalized Unsplittable Flow on Paths with Application to Power Systems Optimization
Authors:
Areg Karapetyan,
Khaled Elbassioni,
Majid Khonji,
Chi-Kin Chau
Abstract:
The Unsplittable Flow on a Path (UFP) problem has garnered considerable attention as a challenging combinatorial optimization problem with notable practical implications. Steered by its pivotal applications in power engineering, the present work formulates a novel generalization of UFP, wherein demands and capacities in the input instance are monotone step functions over the set of edges. As an in…
▽ More
The Unsplittable Flow on a Path (UFP) problem has garnered considerable attention as a challenging combinatorial optimization problem with notable practical implications. Steered by its pivotal applications in power engineering, the present work formulates a novel generalization of UFP, wherein demands and capacities in the input instance are monotone step functions over the set of edges. As an initial step towards tackling this generalization, we draw on and extend ideas from prior research to devise a quasi-polynomial time approximation scheme (QPTAS) under the premise that the demands and capacities lie in a quasi-polynomial range. Second, retaining the same assumption, an efficient logarithmic approximation is introduced for the single-source variant of the problem. Finally, we round up the contributions by designing a (kind of) black-box reduction that, under some mild conditions, allows to translate LP-based approximation algorithms for the studied problem into their counterparts for the Alternating Current Optimal Power Flow (AC OPF) problem -- a fundamental workflow in operation and control of power systems.
△ Less
Submitted 26 October, 2022; v1 submitted 18 September, 2017;
originally announced September 2017.
-
Enumerating Vertices of $0/1$-Polyhedra associated with $0/1$-Totally Unimodular Matrices
Authors:
Khaled Elbassioni,
Kazuhisa Makino
Abstract:
We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron $\mathcal{P}(A,\mathbf{1})=\{x\in\RR^n \mid Ax\geq \b1,~x\geq \b0\}$, when $A$ is a totally unimodular matrix. Our algorithm is based on decomposing the hypergraph transversal problem for unimodular hypergraphs using Seymour's decomposition of totally unimodular matrices, and may be of independent inter…
▽ More
We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron $\mathcal{P}(A,\mathbf{1})=\{x\in\RR^n \mid Ax\geq \b1,~x\geq \b0\}$, when $A$ is a totally unimodular matrix. Our algorithm is based on decomposing the hypergraph transversal problem for unimodular hypergraphs using Seymour's decomposition of totally unimodular matrices, and may be of independent interest.
△ Less
Submitted 12 July, 2017;
originally announced July 2017.
-
Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
Authors:
Rashid Alyassi,
Majid Khonji,
Areg Karapetyan,
Sid Chi-Kin Chau,
Khaled Elbassioni,
Chien-Ming Tseng
Abstract:
Unmanned aerial vehicles (UAVs), commonly known as drones, are being increasingly deployed throughout the globe as a means to streamline monitoring, inspection, mapping, and logistic routines. When dispatched on autonomous missions, drones require an intelligent decision-making system for trajectory planning and tour optimization. Given the limited capacity of their onboard batteries, a key design…
▽ More
Unmanned aerial vehicles (UAVs), commonly known as drones, are being increasingly deployed throughout the globe as a means to streamline monitoring, inspection, mapping, and logistic routines. When dispatched on autonomous missions, drones require an intelligent decision-making system for trajectory planning and tour optimization. Given the limited capacity of their onboard batteries, a key design challenge is to ensure the underlying algorithms can efficiently optimize the mission objectives along with recharging operations during long-haul flights. With this in view, the present work undertakes a comprehensive study on automated tour management systems for an energy-constrained drone: (1) We construct a machine learning model that estimates the energy expenditure of typical multi-rotor drones while accounting for real-world aspects and extrinsic meteorological factors. (2) Leveraging this model, the joint program of flight mission planning and recharging optimization is formulated as a multi-criteria Asymmetric Traveling Salesman Problem (ATSP), wherein a drone seeks for the time-optimal energy-feasible tour that visits all the target sites and refuels whenever necessary. (3) We devise an efficient approximation algorithm with provable worst-case performance guarantees and implement it in a drone management system, which supports real-time flight path tracking and re-computation in dynamic environments. (4) The effectiveness and practicality of the proposed approach are validated through extensive numerical simulations as well as real-world experiments.
△ Less
Submitted 19 April, 2022; v1 submitted 29 March, 2017;
originally announced March 2017.
-
Drive Mode Optimization and Path Planning for Plug-in Hybrid Electric Vehicles
Authors:
Chi-Kin Chau,
Khaled Elbassioni,
Chien-Ming Tseng
Abstract:
Drive modes are driver-selectable pre-set configurations of powertrain and certain vehicle parameters. Plug-in hybrid electric vehicles (PHEVs) typically feature special options of drive modes that can affect the hybrid energy source management system, for example, electric vehicle (EV) mode (that draws fully on battery) and charge sustaining (CS) mode (that utilizes internal combustion engine to…
▽ More
Drive modes are driver-selectable pre-set configurations of powertrain and certain vehicle parameters. Plug-in hybrid electric vehicles (PHEVs) typically feature special options of drive modes that can affect the hybrid energy source management system, for example, electric vehicle (EV) mode (that draws fully on battery) and charge sustaining (CS) mode (that utilizes internal combustion engine to charge battery while propelling the vehicle). This paper studies an optimization problem to enable the driver to select the appropriate drive modes for fuel minimization. We develop optimization algorithms that optimize the decisions of drive modes based on trip information, and integrated with path planning to find an optimal path, considering intermediate filling and charging stations. We further provide an online algorithm that is based on the revealed trip information. We evaluate our algorithms empirically on a Chevrolet Volt, which shows significant fuel savings.
△ Less
Submitted 4 April, 2017; v1 submitted 2 November, 2016;
originally announced November 2016.
-
Online Algorithm for Demand Response with Inelastic Demands and Apparent Power Constraint
Authors:
Areg Karapetyan,
Majid Khonji,
Chi-Kin Chau,
Khaled Elbassioni
Abstract:
A classical problem in power systems is to allocate in-coming (elastic or inelastic) demands without violating the operating constraints of electric networks in an online fashion. Although online decision problems have been well-studied in the literature, a unique challenge arising in power systems is the presence of non-linear constraints, a departure from the traditional settings. A particular e…
▽ More
A classical problem in power systems is to allocate in-coming (elastic or inelastic) demands without violating the operating constraints of electric networks in an online fashion. Although online decision problems have been well-studied in the literature, a unique challenge arising in power systems is the presence of non-linear constraints, a departure from the traditional settings. A particular example is the capacity constraint of apparent power, which gives rise to a quadratic constraint, rather than typical linear constraints. In this paper, we present a competitive randomized online algorithm for deciding whether a sequence of inelastic demands can be allocated for the requested intervals, subject to the total satisfiable apparent power within a time-varying capacity constraint. We also consider an alternative setting with nodal voltage constraint, using a variant of the online algorithm. Finally, simulation studies are provided to evaluate the algorithms empirically.
△ Less
Submitted 25 October, 2021; v1 submitted 2 November, 2016;
originally announced November 2016.
-
A Convex Programming-based Algorithm for Mean Payoff Stochastic Games with Perfect Information
Authors:
Endre Boros,
Khaled Elbassioni,
Vladimir Gurvich,
Kazuhisa Makino
Abstract:
We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph $G = (V, E)$, with local rewards $r: E \to \ZZ$, and three types of positions: black $V_B$, white $V_W$, and random $V_R$ forming a partition of $V$. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, even when $|V_R|=0$. In fact, a pseu…
▽ More
We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph $G = (V, E)$, with local rewards $r: E \to \ZZ$, and three types of positions: black $V_B$, white $V_W$, and random $V_R$ forming a partition of $V$. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, even when $|V_R|=0$. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this short note, we show that BWR-games can be solved via convex programming in pseudo-polynomial time if the number of random positions is a constant.
△ Less
Submitted 21 October, 2016;
originally announced October 2016.
-
Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-dimension
Authors:
Khaled Elbassioni
Abstract:
We consider the problem of finding a small hitting set in an {\it infinite} range space $\cF=(Q,\cR)$ of bounded VC-dimension. We show that, under reasonably general assumptions, the infinite dimensional convex relaxation can be solved (approximately) efficiently by multiplicative weight updates. As a consequence, we get an algorithm that finds, for any $δ>0$, a set of size $O(s_{\cF}(z^*_\cF))$ t…
▽ More
We consider the problem of finding a small hitting set in an {\it infinite} range space $\cF=(Q,\cR)$ of bounded VC-dimension. We show that, under reasonably general assumptions, the infinite dimensional convex relaxation can be solved (approximately) efficiently by multiplicative weight updates. As a consequence, we get an algorithm that finds, for any $δ>0$, a set of size $O(s_{\cF}(z^*_\cF))$ that hits $(1-δ)$-fraction of $\cR$ (with respect to a given measure) in time proportional to $\log(\frac{1}δ)$, where $s_{\cF}(\frac{1}ε)$ is the size of the smallest $ε$-net the range space admits, and $z^*_{\cF}$ is the value of the {\it fractional} optimal solution. This {\it exponentially} improves upon previous results which achieve the same approximation guarantees with running time proportional to $\poly(\frac{1}δ)$. Our assumptions hold, for instance, in the case when the range space represents the {\it visibility} regions of a polygon in $\RR^2$, giving thus a deterministic polynomial time $O(\log z^*_{\cF})$-approximation algorithm for guarding $(1-δ)$-fraction of the area of any given simple polygon, with running time proportional to $\polylog(\frac{1}δ)$.
△ Less
Submitted 13 February, 2017; v1 submitted 12 October, 2016;
originally announced October 2016.
-
Efficient Algorithm for Scalable Event-based Demand Response Management in Microgrids
Authors:
Areg Karapetyan,
Majid Khonji,
Chi-Kin Chau,
Khaled Elbassioni,
H. H. Zeineldin
Abstract:
Demand response management has become one of the key enabling technologies for smart grids. Motivated by the increasing demand response incentives offered by service operators, more customers are subscribing to various demand response programs. However, with growing customer participation, the problem of determining the optimal loads to be curtailed in a microgrid during contingencies within a fea…
▽ More
Demand response management has become one of the key enabling technologies for smart grids. Motivated by the increasing demand response incentives offered by service operators, more customers are subscribing to various demand response programs. However, with growing customer participation, the problem of determining the optimal loads to be curtailed in a microgrid during contingencies within a feasible time frame becomes computationally hard. This paper proposes an efficient approximation algorithm for event-based demand response management in microgrids. In event-based management, it is important to curtail loads as fast as possible to maintain the stability of a microgrid during the islanded mode in a scalable manner. A simple greedy approach is presented that can rapidly determine a close-to-optimal load curtailment scheme to maximize the aggregate customer utility in milliseconds for a large number of customers. This paper further derives a novel theoretical guarantee of the gap between the proposed efficient algorithm and the optimal solution (that may be computationally hard to obtain). The performance of algorithm is corroborated extensively by simulations with up to thousands of customers. For the sake of practicality, the proposed event-based demand response management algorithm is applied to a feeder from the Canadian benchmark distribution system. The simulation results demonstrate that the proposed approach efficiently optimizes microgrid operation during islanded mode while maintaining appropriate voltage levels and network constrains.
△ Less
Submitted 10 October, 2016;
originally announced October 2016.
-
Complex-demand Scheduling Problem with Application in Smart Grid
Authors:
Majid Khonji,
Areg Karapetyan,
Khaled Elbassioni,
Sid Chi-Kin Chau
Abstract:
We consider the problem of scheduling complex-valued demands over a discretized time horizon. Given a set of users, each user is associated with a set of demands representing different power consumption preferences. A demand is represented by a complex number, a time interval, and a utility value obtained if it is satisfied. At each time slot, the magnitude of the total selected demands should not…
▽ More
We consider the problem of scheduling complex-valued demands over a discretized time horizon. Given a set of users, each user is associated with a set of demands representing different power consumption preferences. A demand is represented by a complex number, a time interval, and a utility value obtained if it is satisfied. At each time slot, the magnitude of the total selected demands should not exceed a given generation capacity. This naturally captures the supply constraints in alternating current (AC) electric systems. In this paper, we consider maximizing the aggregate user utility subject to power supply limits over a time horizon. We present approximation algorithms characterized by the maximum angle $φ$ between any two complex-valued demands. More precisely, a PTAS is presented for the case $φ\in [0,\tfracπ{2}]$, a bi-criteria FPTAS for $φ\in [0,π \mbox{-} \varepsilon]$ for any polynomially small $\varepsilon$, assuming the number of time slots in the discretized time horizon is a constant. Furthermore, if the number of time slots is part of the input, we present a reduction to the real-valued unsplittable flow problem on a path with only a constant approximation ratio. Finally, we present a practical greedy algorithm for the single time slot case with an approximation ratio of $\tfrac{1}{2}\cos \fracφ{2}$ and a running time complexity of only ${O}(N\log N)$, $N$ standing for the aggregate number of user demands, which can be implemented efficiently in practice.
△ Less
Submitted 9 October, 2018; v1 submitted 5 March, 2016;
originally announced March 2016.
-
Optimal Power Flow with Inelastic Demands for Demand Response in Radial Distribution Networks
Authors:
Majid Khonji,
Chi-Kin Chau,
Khaled Elbassioni
Abstract:
The classical optimal power flow problem optimizes the power flow in a power network considering the associated flow and operating constraints. In this paper, we investigate optimal power flow in the context of utility-maximizing demand response management in distribution networks, in which customers' demands are satisfied subject to the operating constraints of voltage and transmission power capa…
▽ More
The classical optimal power flow problem optimizes the power flow in a power network considering the associated flow and operating constraints. In this paper, we investigate optimal power flow in the context of utility-maximizing demand response management in distribution networks, in which customers' demands are satisfied subject to the operating constraints of voltage and transmission power capacity. The prior results concern only elastic demands that can be partially satisfied, whereas power demands in practice can be inelastic with binary control decisions, which gives rise to a mixed integer programming problem. We shed light on the hardness and approximability by polynomial-time algorithms for optimal power flow problem with inelastic demands. We show that this problem is inapproximable for general power network topology with upper and lower bounds of nodal voltage. Then, we propose an efficient algorithm for a relaxed problem in radial networks with bounded transmission power loss and upper bound of nodal voltage. We derive an approximation ratio between the proposed algorithm and the exact optimal solution. Simulations show that the proposed algorithm can produce close-to-optimal solutions in practice.
△ Less
Submitted 3 November, 2016; v1 submitted 11 January, 2016;
originally announced January 2016.
-
Quantifying Inefficiency of Fair Cost-Sharing Mechanisms for Sharing Economy
Authors:
Chi-Kin Chau,
Khaled Elbassioni
Abstract:
Sharing economy is a distributed peer-to-peer economic paradigm, which gives rise to a variety of social interactions for economic purposes. One fundamental distributed decision-making process is coalition formation for sharing certain replaceable resources collaboratively, for example, sharing hotel rooms among travelers, sharing taxi-rides among passengers, and sharing regular passes among users…
▽ More
Sharing economy is a distributed peer-to-peer economic paradigm, which gives rise to a variety of social interactions for economic purposes. One fundamental distributed decision-making process is coalition formation for sharing certain replaceable resources collaboratively, for example, sharing hotel rooms among travelers, sharing taxi-rides among passengers, and sharing regular passes among users. Motivated by the applications of sharing economy, this paper studies a coalition formation game subject to the capacity of $K$ participants per coalition. The participants in each coalition are supposed to split the associated cost according to a given cost-sharing mechanism. A stable coalition structure is established when no group of participants can opt out to form another coalition that leads to lower individual payments. We quantify the inefficiency of distributed decision-making processes under a cost-sharing mechanism by the strong price of anarchy (SPoA), comparing a worst-case stable coalition structure and a social optimum. In particular, we derive SPoA for common fair cost-sharing mechanisms (e.g., equal-split, proportional-split, egalitarian and Nash bargaining solutions of bargaining games, and usage based cost-sharing). We show that the SPoA for equal-split, proportional-split, and usage based cost-sharing (under certain conditions) is $Θ(\log K)$, whereas the one for egalitarian and Nash bargaining solutions is $O(\sqrt{K} \log K)$. Therefore, distributed decision-making processes under common fair cost-sharing mechanisms induce only moderate inefficiency.
△ Less
Submitted 16 October, 2017; v1 submitted 16 November, 2015;
originally announced November 2015.
-
A Potential Reduction Algorithm for Two-person Zero-sum Mean Payoff Stochastic Games
Authors:
Endre Boros,
Khaled Elbassioni,
Vladimir Gurvich,
Kazuhisa Makino
Abstract:
We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real $ε$, let us call a stochastic game $ε$-ergodic, if its values from any two initial positions differ by at most $ε$. The proposed new algorithm outputs for every $ε>0$ in finite time either a pair of stationary strategies for the two players guaranteeing that the…
▽ More
We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real $ε$, let us call a stochastic game $ε$-ergodic, if its values from any two initial positions differ by at most $ε$. The proposed new algorithm outputs for every $ε>0$ in finite time either a pair of stationary strategies for the two players guaranteeing that the values from any initial positions are within an $ε$-range, or identifies two initial positions $u$ and $v$ and corresponding stationary strategies for the players proving that the game values starting from $u$ and $v$ are at least $ε/24$ apart. In particular, the above result shows that if a stochastic game is $ε$-ergodic, then there are stationary strategies for the players proving $24ε$-ergodicity. This result strengthens and provides a constructive version of an existential result by Vrieze (1980) claiming that if a stochastic game is $0$-ergodic, then there are $ε$-optimal stationary strategies for every $ε> 0$. The suggested algorithm is based on a potential transformation technique that changes the range of local values at all positions without changing the normal form of the game.
△ Less
Submitted 14 August, 2015;
originally announced August 2015.
-
A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and Few Random Positions
Authors:
Endre Boros,
Khaled Elbassioni,
Vladimir Gurvich,
Kazuhisa Makino
Abstract:
We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph $G = (V, E)$, with local rewards $r: E \to \ZZ$, and three types of positions: black $V_B$, white $V_W$, and random $V_R$ forming a partition of $V$. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not, even when $|V_R|=0$. In fact…
▽ More
We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph $G = (V, E)$, with local rewards $r: E \to \ZZ$, and three types of positions: black $V_B$, white $V_W$, and random $V_R$ forming a partition of $V$. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not, even when $|V_R|=0$. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper, we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with $|V_R|=O(1)$, a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in $|V_W|+|V_B|$, the maximum absolute local reward, and the common denominator of the transition probabilities.
△ Less
Submitted 23 March, 2017; v1 submitted 14 August, 2015;
originally announced August 2015.
-
Truthful Mechanisms for Combinatorial Allocation of Electric Power in Alternating Current Electric Systems for Smart Grid
Authors:
Chi-Kin Chau,
Khaled Elbassioni,
Majid Khonji
Abstract:
Traditional studies of combinatorial auctions often only consider linear constraints. The rise of smart grid presents a new class of auctions, characterized by quadratic constraints. This paper studies the {\em complex-demand knapsack problem}, in which the demands are complex valued and the capacity of supplies is described by the magnitude of total complex-valued demand. This naturally captures…
▽ More
Traditional studies of combinatorial auctions often only consider linear constraints. The rise of smart grid presents a new class of auctions, characterized by quadratic constraints. This paper studies the {\em complex-demand knapsack problem}, in which the demands are complex valued and the capacity of supplies is described by the magnitude of total complex-valued demand. This naturally captures the power constraints in alternating current (AC) electric systems. In this paper, we provide a more complete study and generalize the problem to the multi-minded version, beyond the previously known $\frac{1}{2}$-approximation algorithm for only a subclass of the problem. More precisely, we give a truthful PTAS for the case $φ\in[0,\fracπ{2}-δ]$, and a truthful FPTAS, which {\it fully} optimizes the objective function but violates the capacity constraint by at most $(1+ε)$, for the case $φ\in(\fracπ{2},π-δ]$, where $φ$ is the maximum argument of any complex-valued demand and $ε,δ>0$ are arbitrarily small constants. We complement these results by showing that, unless P=NP, neither a PTAS for the case $φ\in(\fracπ{2},π-δ]$ nor any bi-criteria approximation algorithm with polynomial guarantees for the case when $φ$ is arbitrarily close to $π$ (that is, when $δ$ is arbitrarily close to $0$) can exist.
△ Less
Submitted 3 November, 2016; v1 submitted 7 July, 2015;
originally announced July 2015.
-
A Nested Family of $k$-total Effective Rewards for Positional Games
Authors:
Endre Boros,
Khaled Elbassioni,
Vladimir Gurvich,
Kazuhisa Makino
Abstract:
We consider Gillette's two-person zero-sum stochastic games with perfect information. For each $k \in \ZZ_+$ we introduce an effective reward function, called $k$-total. For $k = 0$ and $1$ this function is known as {\it mean payoff} and {\it total reward}, respectively. We restrict our attention to the deterministic case. For all $k$, we prove the existence of a saddle point which can be realized…
▽ More
We consider Gillette's two-person zero-sum stochastic games with perfect information. For each $k \in \ZZ_+$ we introduce an effective reward function, called $k$-total. For $k = 0$ and $1$ this function is known as {\it mean payoff} and {\it total reward}, respectively. We restrict our attention to the deterministic case. For all $k$, we prove the existence of a saddle point which can be realized by uniformly optimal pure stationary strategies. We also demonstrate that $k$-total reward games can be embedded into $(k+1)$-total reward games.
△ Less
Submitted 14 August, 2015; v1 submitted 20 November, 2014;
originally announced December 2014.
-
Approximation Schemes for Binary Quadratic Programming Problems with Low cp-Rank Decompositions
Authors:
Khaled Elbassioni,
Trung Thanh Nguyen
Abstract:
Binary quadratic programming problems have attracted much attention in the last few decades due to their potential applications. This type of problems are NP-hard in general, and still considered a challenge in the design of efficient approximation algorithms for their solutions. The purpose of this paper is to investigate the approximability for a class of such problems where the constraint matri…
▽ More
Binary quadratic programming problems have attracted much attention in the last few decades due to their potential applications. This type of problems are NP-hard in general, and still considered a challenge in the design of efficient approximation algorithms for their solutions. The purpose of this paper is to investigate the approximability for a class of such problems where the constraint matrices are {\it completely positive} and have low {\it cp-rank}. In the first part of the paper, we show that a completely positive rational factorization of such matrices can be computed in polynomial time, within any desired accuracy. We next consider binary quadratic programming problems of the following form: Given matrices $Q_1,...,Q_n\in\mathbb{R}_+^{n\times n}$, and a system of $m$ constrains $x^TQ_ix\le C_i^2$ ($x^TQ_ix\ge C_i^2$), $i=1,...,m$, we seek to find a vector $x^*\in \{0,1\}^n$ that maximizes (minimizes) a given function $f$. This class of problems generalizes many fundamental problems in discrete optimization such as packing and covering integer programs/knapsack problems, quadratic knapsack problems, submodular maximization, etc. We consider the case when $m$ and the cp-ranks of the matrices $Q_i$ are bounded by a constant.
Our approximation results for the maximization problem are as follows. For the case when the objective function is nonnegative submodular, we give an $(1/4-ε)$-approximation algorithm, for any $ε>0$; when the function $f$ is linear, we present a PTAS. We next extend our PTAS result to a wider class of non-linear objective functions including quadratic functions, multiplicative functions, and sum-of-ratio functions. The minimization problem seems to be much harder due to the fact that the relaxation is {\it not} convex. For this case, we give a QPTAS for $m=1$.
△ Less
Submitted 18 November, 2014;
originally announced November 2014.
-
On Finding Minimal Infrequent Elements in Multi-dimensional Data Defined over Partially Ordered Sets
Authors:
Khaled M. Elbassioni
Abstract:
We consider databases in which each attribute takes values from a partially ordered set (poset). This allows one to model a number of interesting scenarios arising in different applications, including quantitative databases, taxonomies, and databases in which each attribute is an interval representing the duration of a certain event occurring over time. A natural problem that arises in such circum…
▽ More
We consider databases in which each attribute takes values from a partially ordered set (poset). This allows one to model a number of interesting scenarios arising in different applications, including quantitative databases, taxonomies, and databases in which each attribute is an interval representing the duration of a certain event occurring over time. A natural problem that arises in such circumstances is the following: given a database $\mathcal{D}$ and a threshold value $t$, find all collections of "generalizations" of attributes which are "supported" by less than $t$ transactions from $\mathcal{D}$. We call such collections infrequent elements. Due to monotonicity, we can reduce the output size by considering only \emph{minimal} infrequent elements. We study the complexity of finding all minimal infrequent elements for some interesting classes of posets. We show how this problem can be applied to mining association rules in different types of databases, and to finding "sparse regions" or "holes" in quantitative data or in databases recording the time intervals during which a re-occurring event appears over time. Our main focus will be on these applications rather than on the correctness or analysis of the given algorithms.
△ Less
Submitted 9 November, 2014;
originally announced November 2014.
-
A Polynomial Delay Algorithm for Generating Connected Induced Subgraphs of a Given Cardinality
Authors:
Khaled Elbassioni
Abstract:
We give a polynomial delay algorithm, that for any graph $G$ and positive integer $k$, enumerates all connected induced subgraphs of $G$ of order $k$. Our algorithm enumerates each subgraph in at most $O((k\min\{(n-k),kΔ\})^2(Δ+\log k))$ and uses linear space $O(n+m)$, where $n$ and $m$ are respectively the number of vertices and edges of $G$ and $Δ$ is the maximum degree.
We give a polynomial delay algorithm, that for any graph $G$ and positive integer $k$, enumerates all connected induced subgraphs of $G$ of order $k$. Our algorithm enumerates each subgraph in at most $O((k\min\{(n-k),kΔ\})^2(Δ+\log k))$ and uses linear space $O(n+m)$, where $n$ and $m$ are respectively the number of vertices and edges of $G$ and $Δ$ is the maximum degree.
△ Less
Submitted 22 August, 2016; v1 submitted 9 November, 2014;
originally announced November 2014.
-
Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design
Authors:
Khaled Elbassioni,
Kurt Mehlhorn,
Fahimeh Ramezani
Abstract:
R. Lavy and C. Swamy (FOCS 2005, J. ACM 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. Th…
▽ More
R. Lavy and C. Swamy (FOCS 2005, J. ACM 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees.
△ Less
Submitted 14 June, 2016; v1 submitted 7 August, 2014;
originally announced August 2014.
-
Truthful Mechanisms for Combinatorial AC Electric Power Allocation
Authors:
Chi-Kin Chau,
Khaled Elbassioni,
Majid Khonji
Abstract:
Traditional studies of combinatorial auctions often only consider linear constraints (by which the demands for certain goods are limited by the corresponding supplies). The rise of smart grid presents a new class of auctions, characterized by quadratic constraints. Yu and Chau [AAMAS 13'] introduced the complex-demand knapsack problem, in which the demands are complex-valued and the capacity of su…
▽ More
Traditional studies of combinatorial auctions often only consider linear constraints (by which the demands for certain goods are limited by the corresponding supplies). The rise of smart grid presents a new class of auctions, characterized by quadratic constraints. Yu and Chau [AAMAS 13'] introduced the complex-demand knapsack problem, in which the demands are complex-valued and the capacity of supplies is described by the magnitude of total complex-valued demand. This naturally captures the power constraints in AC electric systems. In this paper, we provide a more complete study and generalize the problem to the multi-minded version, beyond the previously known 1/2-approximation algorithm for only a subclass of the problem. More precisely, we give a truthful PTAS for the case phi in [0,pi/2-delta], and a truthful FPTAS, which fully optimizes the objective function but violates the capacity constraint by at most (1+epsilon), for the case phi in (pi/2,pi-delta], where phi is the maximum angle between any two complex-valued demands and epsilon,delta>0 are arbitrarily small constants.
△ Less
Submitted 26 November, 2014; v1 submitted 16 March, 2014;
originally announced March 2014.
-
Approximation Algorithms for Non-Single-minded Profit-Maximization Problems with Limited Supply
Authors:
Khaled Elbassioni,
Mahmoud Fouz,
Chaitanya Swamy
Abstract:
We consider {\em profit-maximization} problems for {\em combinatorial auctions} with {\em non-single minded valuation functions} and {\em limited supply}.
We obtain fairly general results that relate the approximability of the profit-maximization problem to that of the corresponding {\em social-welfare-maximization} (SWM) problem, which is the problem of finding an allocation $(S_1,\ldots,S_n)$…
▽ More
We consider {\em profit-maximization} problems for {\em combinatorial auctions} with {\em non-single minded valuation functions} and {\em limited supply}.
We obtain fairly general results that relate the approximability of the profit-maximization problem to that of the corresponding {\em social-welfare-maximization} (SWM) problem, which is the problem of finding an allocation $(S_1,\ldots,S_n)$ satisfying the capacity constraints that has maximum total value $\sum_j v_j(S_j)$. For {\em subadditive valuations} (and hence {\em submodular, XOS valuations}), we obtain a solution with profit $\OPT_\swm/O(\log c_{\max})$, where $\OPT_\swm$ is the optimum social welfare and $c_{\max}$ is the maximum item-supply; thus, this yields an $O(\log c_{\max})$-approximation for the profit-maximization problem. Furthermore, given {\em any} class of valuation functions, if the SWM problem for this valuation class has an LP-relaxation (of a certain form) and an algorithm "verifying" an {\em integrality gap} of $\al$ for this LP, then we obtain a solution with profit $\OPT_\swm/O(\al\log c_{\max})$, thus obtaining an $O(\al\log c_{\max})$-approximation.
For the special case, when the tree is a path, we also obtain an incomparable $O(\log m)$-approximation (via a different approach) for subadditive valuations, and arbitrary valuations with unlimited supply. Our approach for the latter problem also gives an $\frac{e}{e-1}$-approximation algorithm for the multi-product pricing problem in the Max-Buy model, with limited supply, improving on the previously known approximation factor of 2.
△ Less
Submitted 30 November, 2013;
originally announced December 2013.
-
On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets
Authors:
Khaled Elbassioni,
Kazuhisa Makino,
Kurt Mehlhorn,
Fahimeh Ramezani
Abstract:
Given two bounded convex sets $X\subseteq\RR^m$ and $Y\subseteq\RR^n,$ specified by membership oracles, and a continuous convex-concave function $F:X\times Y\to\RR$, we consider the problem of computing an $\eps$-approximate saddle point, that is, a pair $(x^*,y^*)\in X\times Y$ such that $\sup_{y\in Y} F(x^*,y)\le \inf_{x\in
X}F(x,y^*)+\eps.$ Grigoriadis and Khachiyan (1995) gave a simple rando…
▽ More
Given two bounded convex sets $X\subseteq\RR^m$ and $Y\subseteq\RR^n,$ specified by membership oracles, and a continuous convex-concave function $F:X\times Y\to\RR$, we consider the problem of computing an $\eps$-approximate saddle point, that is, a pair $(x^*,y^*)\in X\times Y$ such that $\sup_{y\in Y} F(x^*,y)\le \inf_{x\in
X}F(x,y^*)+\eps.$ Grigoriadis and Khachiyan (1995) gave a simple randomized variant of fictitious play for computing an $\eps$-approximate saddle point for matrix games, that is, when $F$ is bilinear and the sets $X$ and $Y$ are simplices. In this paper, we extend their method to the general case. In particular, we show that, for functions of constant "width", an $\eps$-approximate saddle point can be computed using $O^*(\frac{(n+m)}{\eps^2}\ln R)$ random samples from log-concave distributions over the convex sets $X$ and $Y$. It is assumed that $X$ and $Y$ have inscribed balls of radius $1/R$ and circumscribing balls of radius $R$. As a consequence, we obtain a simple randomized polynomial-time algorithm that computes such an approximation faster than known methods for problems with bounded width and when $\eps \in (0,1)$ is a fixed, but arbitrarily small constant. Our main tool for achieving this result is the combination of the randomized fictitious play with the recently developed results on sampling from convex sets.
△ Less
Submitted 29 April, 2014; v1 submitted 22 January, 2013;
originally announced January 2013.
-
Geometric Pricing: How Low Dimensionality Helps in Approximability
Authors:
Parinya Chalermsook,
Khaled Elbassioni,
Danupon Nanongkai,
He Sun
Abstract:
Consider the following toy problem. There are $m$ rectangles and $n$ points on the plane. Each rectangle $R$ is a consumer with budget $B_R$, who is interested in purchasing the cheapest item (point) inside R, given that she has enough budget. Our job is to price the items to maximize the revenue. This problem can also be defined on higher dimensions. We call this problem the geometric pricing pro…
▽ More
Consider the following toy problem. There are $m$ rectangles and $n$ points on the plane. Each rectangle $R$ is a consumer with budget $B_R$, who is interested in purchasing the cheapest item (point) inside R, given that she has enough budget. Our job is to price the items to maximize the revenue. This problem can also be defined on higher dimensions. We call this problem the geometric pricing problem.
In this paper, we study a new class of problems arising from a geometric aspect of the pricing problem. It intuitively captures typical real-world assumptions that have been widely studied in marketing research, healthcare economics, etc. It also helps classify other well-known pricing problems, such as the highway pricing problem and the graph vertex pricing problem on planar and bipartite graphs. Moreover, this problem turns out to have close connections to other natural geometric problems such as the geometric versions of the unique coverage and maximum feasible subsystem problems.
We show that the low dimensionality arising in this pricing problem does lead to improved approximation ratios, by presenting sublinear-approximation algorithms for two central versions of the problem: unit-demand uniform-budget min-buying and single-minded pricing problems. Our algorithm is obtained by combining algorithmic pricing and geometric techniques. These results suggest that considering geometric aspect might be a promising research direction in obtaining improved approximation algorithms for such pricing problems. To the best of our knowledge, this is one of very few problems in the intersection between geometry and algorithmic pricing areas. Thus its study may lead to new algorithmic techniques that could benefit both areas.
△ Less
Submitted 24 July, 2012; v1 submitted 13 February, 2012;
originally announced February 2012.
-
On Profit-Maximizing Pricing for the Highway and Tollbooth Problems
Authors:
Khaled Elbassioni,
Rajiv Raman,
Saurabh Ray,
Rene Sitters
Abstract:
In the \emph{tollbooth problem}, we are given a tree $\bT=(V,E)$ with $n$ edges, and a set of $m$ customers, each of whom is interested in purchasing a path on the tree. Each customer has a fixed budget, and the objective is to price the edges of $\bT$ such that the total revenue made by selling the paths to the customers that can afford them is maximized. An important special case of this probl…
▽ More
In the \emph{tollbooth problem}, we are given a tree $\bT=(V,E)$ with $n$ edges, and a set of $m$ customers, each of whom is interested in purchasing a path on the tree. Each customer has a fixed budget, and the objective is to price the edges of $\bT$ such that the total revenue made by selling the paths to the customers that can afford them is maximized. An important special case of this problem, known as the \emph{highway problem}, is when $\bT$ is restricted to be a line.
For the tollbooth problem, we present a randomized $O(\log n)$-approximation, improving on the current best $O(\log m)$-approximation. We also study a special case of the tollbooth problem, when all the paths that customers are interested in purchasing go towards a fixed root of $\bT$. In this case, we present an algorithm that returns a $(1-ε)$-approximation, for any $ε> 0$, and runs in quasi-polynomial time. On the other hand, we rule out the existence of an FPTAS by showing that even for the line case, the problem is strongly NP-hard. Finally, we show that in the \emph{coupon model}, when we allow some items to be priced below zero to improve the overall profit, the problem becomes even APX-hard.
△ Less
Submitted 18 March, 2009; v1 submitted 8 January, 2009;
originally announced January 2009.
-
Improved Approximations for Guarding 1.5-Dimensional Terrains
Authors:
K. Elbassioni,
D. Matijevic,
J. Mestre,
D. Severdija
Abstract:
We present a 4-approximation algorithm for the problem of placing a fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the currently best approximation factor of 5. Our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on d…
▽ More
We present a 4-approximation algorithm for the problem of placing a fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the currently best approximation factor of 5. Our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic problem.
△ Less
Submitted 1 September, 2008;
originally announced September 2008.
-
On Computing the Vertex Centroid of a Polyhedron
Authors:
Khaled Elbassioni,
Hans Raj Tiwary
Abstract:
Let $\mathcal{P}$ be an $\mathcal{H}$-polytope in $\mathbb{R}^d$ with vertex set $V$. The vertex centroid is defined as the average of the vertices in $V$. We prove that computing the vertex centroid of an $\mathcal{H}$-polytope is #P-hard. Moreover, we show that even just checking whether the vertex centroid lies in a given halfspace is already #P-hard for $\mathcal{H}$-polytopes. We also consi…
▽ More
Let $\mathcal{P}$ be an $\mathcal{H}$-polytope in $\mathbb{R}^d$ with vertex set $V$. The vertex centroid is defined as the average of the vertices in $V$. We prove that computing the vertex centroid of an $\mathcal{H}$-polytope is #P-hard. Moreover, we show that even just checking whether the vertex centroid lies in a given halfspace is already #P-hard for $\mathcal{H}$-polytopes. We also consider the problem of approximating the vertex centroid by finding a point within an $ε$ distance from it and prove this problem to be #P-easy by showing that given an oracle for counting the number of vertices of an $\mathcal{H}$-polytope, one can approximate the vertex centroid in polynomial time. We also show that any algorithm approximating the vertex centroid to \emph{any} ``sufficiently'' non-trivial (for example constant) distance, can be used to construct a fully polynomial approximation scheme for approximating the centroid and also an output-sensitive polynomial algorithm for the Vertex Enumeration problem. Finally, we show that for unbounded polyhedra the vertex centroid can not be approximated to a distance of $d^{{1/2}-δ}$ for any fixed constant $δ>0$.
△ Less
Submitted 20 June, 2008;
originally announced June 2008.
-
Characterization of the Vertices and Extreme Directions of the Negative Cycles Polyhedron and Hardness of Generating Vertices of 0/1-Polyhedra
Authors:
Endre Boros,
Khaled Elbassioni,
Vladimir Gurvich,
Hans Raj Tiwary
Abstract:
Given a graph $G=(V,E)$ and a weight function on the edges $w:E\mapsto\RR$, we consider the polyhedron $P(G,w)$ of negative-weight flows on $G$, and get a complete characterization of the vertices and extreme directions of $P(G,w)$. As a corollary, we show that, unless $P=NP$, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-h…
▽ More
Given a graph $G=(V,E)$ and a weight function on the edges $w:E\mapsto\RR$, we consider the polyhedron $P(G,w)$ of negative-weight flows on $G$, and get a complete characterization of the vertices and extreme directions of $P(G,w)$. As a corollary, we show that, unless $P=NP$, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (2006) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes \cite{BL98} [Bussieck and Lübbecke (1998)].
△ Less
Submitted 28 April, 2008; v1 submitted 24 January, 2008;
originally announced January 2008.
-
Upper Bound on the Number of Vertices of Polyhedra with $0,1$-Constraint Matrices
Authors:
Khaled Elbassioni,
Zvi Lotker,
Raimund Seidel
Abstract:
In this note we show that the maximum number of vertices in any polyhedron $P=\{x\in \mathbb{R}^d : Ax\leq b\}$ with $0,1$-constraint matrix $A$ and a real vector $b$ is at most $d!$.
In this note we show that the maximum number of vertices in any polyhedron $P=\{x\in \mathbb{R}^d : Ax\leq b\}$ with $0,1$-constraint matrix $A$ and a real vector $b$ is at most $d!$.
△ Less
Submitted 14 July, 2005;
originally announced July 2005.
