The minimum linear ordering problem (MLOP) seeks to minimize an aggregated cost f(\cdot) due to an ordering \sigma of the items (say [n]), i.e., \min_{\sigma} \sum_{i\in [n]} f(E_{i,\sigma}), where E_{i,\sigma} is the set of items that are mapped by \sigma to indices at most i. This problem has been studied in the literature for various special cases of the cost function f, and in a general setting for a submodular or supermodular cost f [ITT2012]. Though MLOP was known to be NP-hard for general submodular functions, it was unknown whether the special case of graphic matroid MLOP (with f being the matroid rank function of a graph) was polynomial-time solvable. Following this motivation, we explore related classes of linear ordering problems, including symmetric submodular MLOP, minimum latency vertex cover, and minimum sum vertex cover. We show that the most special cases of our problem, graphic matroid MLOP and minimum latency vertex cover, are both NP-hard.

We further expand the toolkit for approximating MLOP variants: using the theory of principal partitions, we show a 2-\frac{1+\ell_{f}}{1+|E|} approximation to monotone submodular MLOP, where \ell_{f}=\frac{f(E)}{\max_{x\in E}f(\{x\})} satisfies 1 \leq \ell_f \leq |E|. Thus our result improves upon the best known bound of 2-\frac{2}{1+|E|} by Iwata, Tetali, and Tripathi [ITT2012]. This leads to a 2-\frac{1+r(E)}{1+|E|} approximation for the matroid MLOP, corresponding to the case when r is the rank function of a given matroid. Finally, we show that MLVC can be 4/3 approximated, matching the integrality gap of its vanilla LP relaxation.

We study the Quantum Approximate Optimization Algorithm (QAOA) in the context of the Max-Cut problem. Near-term (noisy) quantum devices are only able to (accurately) execute QAOA at low circuit depths while QAOA requires a relatively high circuit-depth in order to "see" the whole graph. We introduce a classical pre-processing step that initializes QAOA with a biased superposition of all possible cuts in the graph, referred to as a warm-start. In particular, our initialization informs QAOA by a solution to a low-rank semidefinite programming relaxation of the Max-Cut problem. Our experimental results show that this variant of QAOA, called QAOA-Warm, is able to outperform standard QAOA on lower circuit depths with less training time (in the optimization stage for QAOA's variational parameters). We provide experimental evidence as well as theoretical intuition on performance of the proposed framework.

We studied variants of the Traveling Salesman Problem whose objective can be more efficient, fair, and adjustable to various applications, e.g., ride-sharing from costumer vs server perspective, containment of wildfires, etc. In contrast to path-TSP, we generalize the objective to be an arbitrary norm of the delay/service-time vector.

We developed efficient randomized algorithms with approximate optimality guarantees for such APX-hard problems in general metrics.

We also provided an approximation preserving reduction from the problem with any Minkowski norm of the delay vector as the (non-linear) objective, to a variant of TSP with a constant number of deadlines.

In min sum vertex cover (MSVC) the goal is to find an ordering of the vertices of a graph to minimize the average cover time of its edges. An edge is covered when one of its endpoints appears in the ordering. We give a 16/9 = 1.778 approximation for MSVC, and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best 1.999946 approximation of Barenholz, Feige and Peleg.

We also study a much more general problem known as multiple intents ranking, or generalized min sum set cover (GMSSC), wherein given a hypergraph, each hyperedge is considered covered by the first time when a given number of its vertices appear in the ordering. We give a 4.642 approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case of min sum set cover (MSSC) studied by Feige, Lovász and Tetali, and improving upon the previous best known bound of 12.4 due to Im, Sviridenko and van der Zwaan.

Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. This also gives an LP-based 4 approximation for MSSC. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility.

We presented a low complexity while accurate Heart Rate (HR) estimation technique from signals captured by Photoplethysmographic (PPG) sensors worn on the wrist during intensive physical exercise. Wrist-type PPG signals experience severe Motion Artifacts (MA) that hinder efficient HR estimation especially during intensive physical exercises. To suppress the motion artifacts efficiently, simultaneous 3 dimensional acceleration signals are used as reference MAs.

We introduced heuristics to recover, denoise, and post-process the spectrum of the heart beat signal, to track and predict HR time series.

The proposed method achieved an Average Absolute Error (AAE) of 1.19 Beats Per Minute (BPM) on the 12 benchmark PPG recordings in which subjects run at speeds of up to 15 km/h. This method also achieves an AAE of 2.17 BPM on the whole benchmark database of 23 recordings that include both running and arm movement activities.

The proposed method achieved comparable accuracy with state-of-the-art algorithms while at a significantly reduced computational cost which makes its standalone implementation on wearable devices feasible. The proposed algorithm achieves an average processing time of 32 milliseconds per input frames of length 8 seconds (2 channel PPG and 3D ACC signals) on a 3.2 GHz processor.

We presented a local and arbitrary precise routing scheme for the well-separated pair decomposition (WSPD) spanners, using compressed quadtrees. Given a point set P in the plane, a WSPD spanner is a geometric graph whose vertex set is P, and for each pair (A, B) in the WSPD of P, an edge is added to the graph from an arbitrary point in A to an arbitrary point in B.

We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among n players in a way that meets the following criteria: (I) every player(weakly) prefers his allocated cake to any other player’s share (such notion is known as envy-freeness), (II) the mechanism is strategy-proof (truthful), and (III) the number of cuts made on the cake is minimal. We provide methods, namely expansion process and expansion process with unlocking, for dividing the cake under different assumptions on the valuation functions of the players.

We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among n players in a way that meets the following criteria: (I) every player(weakly) prefers his allocated cake to any other player’s share (such notion is known as envy-freeness), (II) the mechanism is strategy-proof (truthful), and (III) the number of cuts made on the cake is minimal. We provide methods, namely expansion process and expansion process with unlocking, for dividing the cake under different assumptions on the valuation functions of the players.

Given a set S of points in a metric space, and a diversity measure div (.) defined over subsets of S, the goal of the diversity maximization problem is to find a subset T of size k that maximizes div(T). Motivated by applications in massive data processing, we consider the composable coreset framework in which a coreset for a diversity measure is called composable, if for any collection of sets and their corresponding coresets, the maximum diversity of the union of the coresets approximates the maximum diversity of the union of the sets. We present composable coresets with near-optimal approximation factors for several notions of diversity, including remote-clique, remote-cycle, and remote-tree. We also prove a general lower bound on the approximation factor of composable coresets for a large class of diversity maximization problems.