Search

The classic house allocation problem involves assigning $m$ houses to $n$ agents based on their utility functions, ensuring each agent receives exactly one house. A key criterion in these problems is satisfying fairness constraints such as envy-freeness. We extend this problem by considering agents with arbitrary weights, focusing on the concept of weighted envy-freeness, which has been extensively studied in fair division. We present a polynomial-time algorithm to determine whether weighted envy-free allocations exist and, if so, to compute one. Since weighted envy-free allocations do not always exist, we also investigate the potential of achieving such allocations through the use of subsidies. We provide several characterizations for weighted envy-freeable allocations (allocations that can be turned weighted envy-free by introducing subsidies) and show that they do not always exist, which is different from the unweighted setting. Furthermore, we explore the existence of weighted envy-freeable allocations in specific scenarios and outline the conditions under which they exist., Comment: 17 pages, 4 figures

We consider the problem of allocating $m$ indivisible items to a set of $n$ heterogeneous agents, aiming at computing a proportional allocation by introducing subsidy (money). It has been shown by Wu et al. (WINE 2023) that when agents are unweighted a total subsidy of $n/4$ suffices (assuming that each item has value/cost at most $1$ to every agent) to ensure proportionality. When agents have general weights, they proposed an algorithm that guarantees a weighted proportional allocation requiring a total subsidy of $(n-1)/2$, by rounding the fractional bid-and-take algorithm. In this work, we revisit the problem and the fractional bid-and-take algorithm. We show that by formulating the fractional allocation returned by the algorithm as a directed tree connecting the agents and splitting the tree into canonical components, there is a rounding scheme that requires a total subsidy of at most $n/3 - 1/6$., Comment: 30 pages, 11 figures

We study the problem of allocating a group of indivisible chores among agents while each chore has a binary marginal. We focus on the fairness criteria of envy-freeness up to any item (EFX) and investigate the existence of EFX allocations. We show that when agents have additive binary cost functions, there exist EFX and Pareto-optimal (PO) allocations that can be computed in polynomial time. To the best of our knowledge, this is the first setting of a general number of agents that admits EFX and PO allocations, before which EFX and PO allocations have only been shown to exist for three bivalued agents. We further consider more general cost functions: cancelable and general monotone (both with binary marginal). We show that EFX allocations exist and can be computed for binary cancelable chores, but EFX is incompatible with PO. For general binary marginal functions, we propose an algorithm that computes (partial) envy-free (EF) allocations with at most $n-1$ unallocated items., Comment: 11 pages, 1 figure

We consider the problem of fair allocation of $m$ indivisible items to a group of $n$ agents with subsidy (money). Our work mainly focuses on the allocation of chores but most of our results extend to the allocation of goods as well. We consider the case when agents have (general) additive cost functions. Assuming that the maximum cost of an item to an agent can be compensated by one dollar, we show that a total of $n/4$ dollars of subsidy suffices to ensure a proportional allocation. Moreover, we show that $n/4$ is tight in the sense that there exists an instance with $n$ agents for which every proportional allocation requires a total subsidy of at least $n/4$. We also consider the weighted case and show that a total subsidy of $(n-1)/2$ suffices to ensure a weighted proportional allocation., Comment: 24 pages, 4 figures

We consider the online bipartite matching problem on $(k,d)$-bounded graphs, where each online vertex has at most $d$ neighbors, each offline vertex has at least $k$ neighbors, and $k\geq d\geq 2$. The model of $(k,d)$-bounded graphs is proposed by Naor and Wajc (EC 2015 and TEAC 2018) to model the online advertising applications in which offline advertisers are interested in a large number of ad slots, while each online ad slot is interesting to a small number of advertisers. They proposed deterministic and randomized algorithms with a competitive ratio of $1 - (1-1/d)^k$ for the problem, and show that the competitive ratio is optimal for deterministic algorithms. They also raised the open questions of whether strictly better competitive ratios can be achieved using randomized algorithms, for both the adversarial and stochastic arrival models. In this paper we answer both of their open problems affirmatively. For the adversarial arrival model, we propose a randomized algorithm with competitive ratio $1 - (1-1/d)^k + \Omega(d^{-4}\cdot e^{-\frac{k}{d}})$ for all $k\geq d\geq 2$. We also consider the stochastic model and show that even better competitive ratios can be achieved. We show that for all $k\geq d\geq 2$, the competitive ratio is always at least $0.8237$. We further consider the $b$-matching problem when each offline vertex can be matched at most $b$ times, and provide several competitive ratio lower bounds for the adversarial and stochastic model., Comment: Some error was discovered in the analysis for the stochastic setting

We consider the problem of fairly allocating a sequence of indivisible items that arrive online in an arbitrary order to a group of n agents with additive normalized valuation functions. We consider both the allocation of goods and chores and propose algorithms for approximating maximin share (MMS) allocations. When agents have identical valuation functions the problem coincides with the semi-online machine covering problem (when items are goods) and load balancing problem (when items are chores), for both of which optimal competitive ratios have been achieved. In this paper, we consider the case when agents have general additive valuation functions. For the allocation of goods, we show that no competitive algorithm exists even when there are only three agents and propose an optimal 0.5-competitive algorithm for the case of two agents. For the allocation of chores, we propose a (2-1/n)-competitive algorithm for n>=3 agents and a square root of 2 (approximately 1.414)-competitive algorithm for two agents. Additionally, we show that no algorithm can do better than 15/11 (approximately 1.364)-competitive for two agents., Comment: 29 pages, 1 figure (to appear in ICML 2023)

We consider the edge-weighted online stochastic matching problem, in which an edge-weighted bipartite graph G=(I\cup J, E) with offline vertices J and online vertex types I is given. The online vertices have types sampled from I with probability proportional to the arrival rates of online vertex types. The online algorithm must make immediate and irrevocable matching decisions with the objective of maximizing the total weight of the matching. For the problem with general arrival rates, Feldman et al. (FOCS 2009) proposed the Suggested Matching algorithm and showed that it achieves a competitive ratio of 1-1/e \approx 0.632. The ratio has recently been improved to 0.645 by Yan (2022), who proposed the Multistage Suggested Matching (MSM) algorithm. In this paper, we propose the Evolving Suggested Matching (ESM) algorithm, and show that it achieves a competitive ratio of 0.650.

We study how to fairly allocate a set of indivisible chores to a group of agents, where each agent $i$ has a non-negative weight $w_i$ that represents its obligation for undertaking the chores. We consider the fairness notion of weighted envy-freeness up to one item (WEF1) and propose an efficient picking sequence algorithm for computing WEF1 allocations. Our analysis is based on a natural and powerful continuous interpretation for the picking sequence algorithms in the weighted setting, which might be of independent interest. Using this interpretation, we establish the necessary and sufficient conditions under which picking sequence algorithms can guarantee other fairness notions in the weighted setting. We also study the existence of fair and efficient allocations and propose efficient algorithms for the computation of WEF1 and PO allocations for the bi-valued instances. Our result generalizes that of Garg et al. (AAAI 2022) and Ebadian et al. (AAMAS 2022) to the weighted setting. Our work also studies the price of fairness for WEF1, and the implications of WEF1 to other fairness notions., Comment: 26 pages, 2 figures

Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than $((1-o(1))\ln k)$-approximation polynomial-time algorithms unless P=NP, where $k$ is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents' rankings on the edges. Finally, we extend our results to submodular objective functions and Matroid rank constraints., Comment: To appear in AAAI 2023

Currently, deep learning methods with stacking small size convolutional filters are widely used for automatic modulation classification (AMC). In this report, we find some experienced improvements by using large kernel size for convolutional deep convolution neural network based AMC, which is more efficient in extracting multi-scale features of the raw signal I/Q sequence data. Also, Squeeze-and-Excitation (SE) mechanisms can significantly help AMC networks to focus on the more important features of the signal. As a result, we propose a multi-scale feature network with large kernel size and SE mechanism (SE-MSFN) in this paper. SE-MSFN achieves state-of-the-art classification performance on the public well-known RADIOML 2018.01A dataset, with average classification accuracy of 64.50%, surpassing CLDNN by 1.42%, maximum classification accuracy of 98.5%, and an average classification accuracy of 85.53% in the lower SNR range 0dB to 10dB, surpassing CLDNN by 2.85%. In addition, we also verified that ensemble learning can help further improve classification performance. We hope this report can provide some references for developers and researchers in practical scenes., Comment: Accepted by IJCNN2022

Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research., Comment: This survey unifies and extends preliminary versions that appeared in IJCAI 2022 (arXiv:2202.07551) and SIGecom Exchanges (arXiv:2202.08713). It has been accepted for publication to the journal of Artificial Intelligence (AIJ)

In this work, we study the single-choice prophet inequality problem, where a gambler faces a sequence of~$n$ online i.i.d. random variables drawn from an unknown distribution. When a variable reveals its value, the gambler needs to decide irrevocably whether or not to accept the value. The goal is to maximize the competitive ratio between the expected gain of the gambler and that of the maximum variable. It is shown by Correa et al. that when the distribution is unknown or only $o(n)$ uniform samples from the distribution are given, the best an algorithm can do is $1/e$-competitive. In contrast, when the distribution is known or $\Omega(n)$ uniform samples are given, the optimal competitive ratio of 0.7451 can be achieved. In this paper, we study a new model in which the algorithm has access to an oracle that answers quantile queries about the distribution and investigate to what extent we can use a small number of queries to achieve good competitive ratios. We first use the answers from the queries to implement the threshold-based algorithms and show that with two thresholds our algorithm achieves a competitive ratio of $0.6786$. Motivated by the two-threshold algorithm, we design the observe-and-accept algorithm that requires only a single query. This algorithm sets a threshold in the first phase by making a query and uses the maximum realization from the first phase as the threshold for the second phase. It can be viewed as a natural combination of the single-threshold algorithm and the algorithm for the secretary problem. By properly choosing the quantile to query and the break-point between the two phases, we achieve a competitive ratio of $0.6718$, beating the benchmark of $1-1/e$., Comment: 32 pages, 2 figures

The Stackelberg security game is played between a defender and an attacker, where the defender needs to allocate a limited amount of resources to multiple targets in order to minimize the loss due to adversarial attack by the attacker. While allowing targets to have different values, classic settings often assume uniform requirements to defend the targets. This enables existing results that study mixed strategies (randomized allocation algorithms) to adopt a compact representation of the mixed strategies. In this work, we initiate the study of mixed strategies for the security games in which the targets can have different defending requirements. In contrast to the case of uniform defending requirement, for which an optimal mixed strategy can be computed efficiently, we show that computing the optimal mixed strategy is NP-hard for the general defending requirements setting. However, we show that strong upper and lower bounds for the optimal mixed strategy defending result can be derived. We propose an efficient close-to-optimal Patching algorithm that computes mixed strategies that use only few pure strategies. We also study the setting when the game is played on a network and resource sharing is enabled between neighboring targets. Our experimental results demonstrate the effectiveness of our algorithm in several large real-world datasets., Comment: Accepted by IJCAI-2022

The theory of algorithmic fair allocation is within the center of multi-agent systems and economics in the last decade due to its industrial and social importance. At a high level, the problem is to assign a set of items that are either goods or chores to a set of agents so that every agent is happy with what she obtains. Particularly, in this survey, we focus on indivisible items, for which absolute fairness such as envy-freeness and proportionality cannot be guaranteed. One main theme in the recent research agenda is about designing algorithms that approximately achieve the fairness criteria. We aim at presenting a comprehensive survey of recent progresses through the prism of algorithms, highlighting the ways to relax fairness notions and common techniques to design algorithms, as well as the most interesting questions for future research.

A new class of spatially-coupled turbo-like codes (SC-TCs), dubbed generalized spatially coupled parallel concatenated codes (GSC-PCCs), is introduced. These codes are constructed by applying spatial coupling on parallel concatenated codes (PCCs) with a fraction of information bits repeated $q$ times. GSC-PCCs can be seen as a generalization of the original spatially-coupled parallel concatenated codes proposed by Moloudi et al. [2]. To characterize the asymptotic performance of GSC-PCCs, we derive the corresponding density evolution equations and compute their decoding thresholds. The threshold saturation effect is observed and proven. Most importantly, we rigorously prove that any rate-$R$ GSC-PCC ensemble with 2-state convolutional component codes achieves at least a fraction $1-\frac{R}{R+q}$ of the capacity of the binary erasure channel (BEC) for repetition factor $q\geq2$ and this multiplicative gap vanishes as $q$ tends to infinity. To the best of our knowledge, this is the first class of SC-TCs that are proven to be capacity-achieving. Further, the connection between the strength of the component codes, the decoding thresholds of GSC-PCCs, and the repetition factor are established. The superiority of the proposed codes with finite blocklength is exemplified by comparing their error performance with that of existing SC-TCs via computer simulations., Comment: Revised version, 36 pages, 10 figures, 4 tables. arXiv admin note: text overlap with arXiv:2105.00698

In this paper, we study how to fairly allocate a set of m indivisible chores to a group of n agents, each of which has a general additive cost function on the items. Since envy-free (EF) allocations are not guaranteed to exist, we consider the notion of envy-freeness up to any item (EFX). In contrast to the fruitful results regarding the (approximation of) EFX allocations for goods, very little is known for the allocation of chores. Prior to our work, for the allocation of chores, it is known that EFX allocations always exist for two agents or general number of agents with identical ordering cost functions. For general instances, no non-trivial approximation result regarding EFX allocation is known. In this paper, we make progress in this direction by providing several polynomial time algorithms for the computation of EFX and approximately EFX allocations. We show that for three agents we can always compute a 4.45-approximation of EFX allocation. For n>=4 agents, our algorithm always computes a (3n^2-n)-approximation. We also study the bi-valued instances, in which agents have at most two cost values on the chores. For three agents, we provide an algorithm for the computation of EFX allocations. For n>=4 agents, we present algorithms for the computation of partial EFX allocations with at most n-1 unallocated items; and (n-1)-approximation of EFX allocations., Comment: Include new results about partial EFX allocations and improved results regarding approximate EFX allocations

In the budget-feasible allocation problem, a set of items with varied sizes and values are to be allocated to a group of agents. Each agent has a budget constraint on the total size of items she can receive. The goal is to compute a feasible allocation that is envy-free (EF), in which the agents do not envy each other for the items they receive, nor do they envy a charity, who is endowed with all the unallocated items. Since EF allocations barely exist even without budget constraints, we are interested in the relaxed notion of envy-freeness up to one item (EF1). The computation of both exact and approximate EF1 allocations remains largely open, despite a recent effort by Wu et al. (IJCAI 2021) in showing that any budget-feasible allocation that maximizes the Nash Social Welfare (NSW) is 1/4-approximate EF1. In this paper, we move one step forward by showing that for agents with identical additive valuations, a 1/2-approximate EF1 allocation can be computed in polynomial time. For the uniform-budget and two-agent cases, we propose efficient algorithms for computing an exact EF1 allocation. We also consider the large budget setting, i.e., when the item sizes are infinitesimal compared with the agents' budgets, and show that both the NSW maximizing allocation and the allocation our polynomial-time algorithm computes have an approximation close to 1 regarding EF1.

We introduce generalized spatially coupled parallel concatenated codes (GSC-PCCs), a class of spatially coupled turbo-like codes obtained by coupling parallel concatenated codes (PCCs) with a fraction of information bits repeated before the PCC encoding. GSC-PCCs can be seen as a generalization of the original spatially coupled parallel concatenated convolutional codes (SC-PCCs) proposed by Moloudi et al. [1]. To characterize the asymptotic performance of GSC-PCCs, we derive the corresponding density evolution equations and compute their decoding thresholds. We show that the proposed codes have some nice properties such as threshold saturation and that their decoding thresholds improve with the repetition factor $q$. Most notably, our analysis suggests that the proposed codes asymptotically approach the capacity as $q$ tends to infinity with any given constituent convolutional code., Comment: 6 pages, 3 figures, accepted by the 2021 IEEE International Symposium on Information Theory

In this paper, we study how to fairly allocate m indivisible chores to n (asymmetric) agents. We consider (weighted) proportionality up to any item (PROPX) and show that a (weighted) PROPX allocation always exists and can be computed efficiently. For chores, we argue that PROPX might be a more reliable relaxation for proportionality by the facts that any PROPX allocation ensures 2-approximation of maximin share (MMS) fairness [Budish, 2011] for symmetric agents and of anyprice share (APS) fairness [Babaioff et al, 2021] for asymmetric agents. APS allocations for chores have not been studied before the current work, and our result implies a 2-approximation algorithm. Another by-product result is that an EFX and a weighted EF1 allocation for indivisible chores exist if all agents have the same ordinal preference, which might be of independent interest. We then consider the partial information setting and design algorithms that only use agents' ordinal preferences to compute approximately PROPX allocations. Our algorithm achieves a 2-approximation for both symmetric and asymmetric agents, and the approximation ratio is optimal. Finally, we study the price of fairness (PoF), i.e., the loss in social welfare by enforcing allocations to be (weighted) PROPX. We prove that the tight ratio for PoF is Theta(n) for symmetric agents and unbounded for asymmetric agents.

We initiate the work on maximin share (MMS) fair allocation of m indivisible chores to n agents using only their ordinal preferences, from both algorithmic and mechanism design perspectives. The previous best-known approximation is 2-1/n by Aziz et al. [IJCAI 2017]. We improve this result by giving a simple deterministic 5/3-approximation algorithm that determines an allocation sequence of agents, according to which items are allocated one by one. By a tighter analysis, we show that for n=2,3, our algorithm achieves better approximation ratios, and is actually optimal. We also consider the setting with strategic agents, where agents may misreport their preferences to manipulate the outcome. We first provide a O(\log (m/n))-approximation consecutive picking algorithm, and then improve the approximation ratio to O(\sqrt{\log n}) by a randomized algorithm. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods., Comment: arXiv admin note: text overlap with arXiv:1905.08925

In this paper, we study a class of spatially coupled turbo codes, namely partially information- and partially parity-coupled turbo codes. This class of codes enjoy several advantages such as flexible code rate adjustment by varying the coupling ratio and the encoding and decoding architectures of the underlying component codes can remain unchanged. For this work, we first provide the construction methods for partially coupled turbo codes with coupling memory $m$ and study the corresponding graph models. We then derive the density evolution equations for the corresponding ensembles on the binary erasure channel to precisely compute their iterative decoding thresholds. Rate-compatible designs and their decoding thresholds are also provided, where the coupling and puncturing ratios are jointly optimized to achieve the largest decoding threshold for a given target code rate. Our results show that for a wide range of code rates, the proposed codes attain close-to-capacity performance and the decoding performance improves with increasing the coupling memory. In particular, the proposed partially parity-coupled turbo codes have thresholds within 0.0002 of the BEC capacity for rates ranging from $1/3$ to $9/10$, yielding an attractive way for constructing rate-compatible capacity-approaching channel codes., Comment: 15 pages, 13 figures. Accepted for publication in IEEE Transactions on Communications

The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget-feasible allocation problem, in which each item has a cost that will be incurred to the agent it is allocated to, and each agent has a budget constraint on the total cost of items she receives. We show that a budget-feasible allocation that maximizes the NSW achieves a 1/4-approximation of EF1 and the approximation ratio is tight. The approximation ratio improves gracefully when the items have small costs compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity., Comment: 16 pages, 2 figures

In classic network security games, the defender distributes defending resources to the nodes of the network, and the attacker attacks a node, with the objective to maximize the damage caused. Existing models assume that the attack at node u causes damage only at u. However, in many real-world security scenarios, the attack at a node u spreads to the neighbors of u and can cause damage at multiple nodes, e.g., for the outbreak of a virus. In this paper, we consider the network defending problem against contagious attacks. Existing works that study shared resources assume that the resource allocated to a node can be shared or duplicated between neighboring nodes. However, in real world, sharing resource naturally leads to a decrease in defending power of the source node, especially when defending against contagious attacks. To this end, we study the model in which resources allocated to a node can only be transferred to its neighboring nodes, which we refer to as a reallocation process. We show that this more general model is difficult in two aspects: (1) even for a fixed allocation of resources, we show that computing the optimal reallocation is NP-hard; (2) for the case when reallocation is not allowed, we show that computing the optimal allocation (against contagious attack) is also NP-hard. For positive results, we give a mixed integer linear program formulation for the problem and a bi-criteria approximation algorithm. Our experimental results demonstrate that the allocation and reallocation strategies our algorithm computes perform well in terms of minimizing the damage due to contagious attacks., Comment: 9 pages; AAAI 2021

Partially information coupled turbo codes (PIC-TCs) is a class of spatially coupled turbo codes that can approach the BEC capacity while keeping the encoding and decoding architectures of the underlying component codes unchanged. However, PIC-TCs have significant rate loss compared to its component rate-1/3 turbo code, and the rate loss increases with the coupling ratio. To absorb the rate loss, in this paper, we propose the partially information coupled duo-binary turbo codes (PIC-dTCs). Given a rate-1/3 turbo code as the benchmark, we construct a duo-binary turbo code by introducing one extra input to the benchmark code. Then, parts of the information sequence from the original input are coupled to the extra input of the succeeding code blocks. By looking into the graph model of PIC-dTC ensembles, we derive the exact density evolution equations of the PIC-dTC ensembles, and compute their belief propagation decoding thresholds on the binary erasure channel. Simulation results verify the correctness of our theoretical analysis, and also show significant error performance improvement over the uncoupled rate-1/3 turbo codes and existing designs of spatially coupled turbo codes., Comment: Accepted at the ISIT 2020

Karp, Vazirani, and Vazirani (STOC 1990) initiated the study of online bipartite matching, which has held a central role in online algorithms ever since. Of particular importance are the Ranking algorithm for integral matching and the Water-filling algorithm for fractional matching. Most algorithms in the literature can be viewed as adaptations of these two in the corresponding models. Recently, Huang et al.~(STOC 2018, SODA 2019) introduced a more general model called \emph{fully online matching}, which considers general graphs and allows all vertices to arrive online. They also generalized Ranking and Water-filling to fully online matching and gave some tight analysis: Ranking is $\Omega \approx 0.567$-competitive on bipartite graphs where the $\Omega$-constant satisfies $\Omega e^\Omega = 1$, and Water-filling is $2-\sqrt{2} \approx 0.585$-competitive on general graphs. We propose fully online matching algorithms strictly better than Ranking and Water-filling. For integral matching on bipartite graphs, we build on the online primal dual analysis of Ranking and Water-filling to design a $0.569$-competitive hybrid algorithm called Balanced Ranking. To our knowledge, it is the first integral algorithm in the online matching literature that successfully integrates ideas from Water-filling. For fractional matching on general graphs, we give a $0.592$-competitive algorithm called Eager Water-filling, which may match a vertex on its arrival. By contrast, the original Water-filling algorithm always matches vertices at their deadlines. Our result for fractional matching further shows a separation between fully online matching and the general vertex arrival model by Wang and Wong (ICALP 2015), due to an upper bound of $0.5914$ in the latter model by Buchbinder, Segev, and Tkach (ESA 2017).

In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal $\min(O(\log n), f)$ approximation factor. (Throughout, $m$, $n$, $f$, and $C$ are parameters denoting the maximum number of sets, number of elements, frequency, and the cost range.) In the high-frequency range, when $f=\Omega(\log n)$, this was achieved by a deterministic $O(\log n)$-approximation algorithm with $O(f \log n)$ amortized update time [Gupta et al. STOC'17]. In the low-frequency range, the line of work by Gupta et al. [STOC'17], Abboud et al. [STOC'19], and Bhattacharya et al. [ICALP'15, IPCO'17, FOCS'19] led to a deterministic $(1+\epsilon)f$-approximation algorithm with $O(f \log (Cn)/\epsilon^2)$ amortized update time. In this paper we improve the latter update time and provide the first bounds that subsume (and sometimes improve) the state-of-the-art dynamic vertex cover algorithms. We obtain: 1. $(1+\epsilon)f$-approximation ratio in $O(f\log^2 (Cn)/\epsilon^3)$ worst-case update time: No non-trivial worst-case update time was previously known for dynamic set cover. Our bound subsumes and improves by a logarithmic factor the $O(\log^3 n/\text{poly}(\epsilon))$ worst-case update time for unweighted dynamic vertex cover (i.e., when $f=2$ and $C=1$) by Bhattacharya et al. [SODA'17]. 2. $(1+\epsilon)f$-approximation ratio in $O\left((f^2/\epsilon^3)+(f/\epsilon^2) \log C\right)$ amortized update time: This result improves the previous $O(f \log (Cn)/\epsilon^2)$ update time bound for most values of $f$ in the low-frequency range, i.e. whenever $f=o(\log n)$. It is the first that is independent of $m$ and $n$. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [SODA'19] for unweighted dynamic vertex cover (i.e., when $f = 2$ and $C = 1$)., Comment: This new version contains an additional result on worst-case update time and a revised extended abstract

We study the oblivious matching problem, which aims at finding a maximum matching on a graph with unknown edge set. Any algorithm for the problem specifies an ordering of the vertex pairs. The matching is then produced by probing the pairs following the ordering, and including a pair if both of them are unmatched and there exists an edge between them. The unweighted (Chan et al. (SICOMP 2018)) and the vertex-weighted (Chan et al. (TALG 2018)) versions of the problem are well studied. In this paper, we consider the edge-weighted oblivious matching problem on bipartite graphs, which generalizes the stochastic bipartite matching problem. Very recently, Gamlath et al. (SODA 2019) studied the stochastic bipartite matching problem, and proposed an (1-1/e)-approximate algorithm. We give a very simple algorithm adapted from the Ranking algorithm by Karp et al. (STOC 1990), and show that it achieves the same (1-1/e) approximation ratio for the oblivious matching problem on bipartite graph., Comment: 5 pages

We develop an effective computer model to simulate sensing environments that consist of natural trees. The simulated environments are random and contain full geometry of the tree foliage. While this simulated model can be used as a general platform for studying the sensing mechanism of different flying species, our ultimate goal is to build bat-inspired Quad-rotor UAVs- UAVs that can recreate bat's flying behavior (e.g., obstacle avoidance, path planning) in dense vegetation. To this end, we also introduce an foliage echo simulator that can produce simulated echoes by mimicking bat's biosonar. In our current model, a few realistic model choices or assumptions are made. First, in order to create natural looking trees, the branching structures of trees are modeled by L-systems, whereas the detailed geometry of branches, sub-branches and leaves is created by randomizing a reference tree in a CAD object file. Additionally, the foliage echo simulator is simplified so that no shading effect is considered. We demonstrate our developed model by simulating real-world scenarios with multiple trees and compute the corresponding impulse responses along a Quad-rotor trajectory., Comment: Accepted for presentation at International Florida AI Research Society (FLAIRS) Conference 2020

In this article, we propose a new approach for simulating trees, including their branches, sub-branches, and leaves. This approach combines the theory of biological development, mathematical models, and computer graphics, producing simulated trees and forest with full geometry. Specifically, we adopt the Lindenmayer process to simulate the branching pattern of trees and modify the available measurements and dimensions of 3D CAD developed object files to create natural looking sub-branches and leaves. Randomization has been added to the placement of all branches, sub branches and leaves. To simulate a forest, we adopt Inhomogeneous Poisson process to generate random locations of trees. Our approach can be used to create complex structured 3D virtual environment for the purpose of testing new sensors and training robotic algorithms. We look forward to applying this approach to test biosonar sensors that mimick bats' fly in the simulated environment., Comment: Accepted for presentation at Information and Computer Technologies (ICICT 2020)

In this paper we consider a defending problem on a network. In the model, the defender holds a total defending resource of R, which can be distributed to the nodes of the network. The defending resource allocated to a node can be shared by its neighbors. There is a weight associated with every edge that represents the efficiency defending resources are shared between neighboring nodes. We consider the setting when each attack can affect not only the target node, but its neighbors as well. Assuming that nodes in the network have different treasures to defend and different defending requirements, the defender aims at allocating the defending resource to the nodes to minimize the loss due to attack. We give polynomial time exact algorithms for two important special cases of the network defending problem. For the case when an attack can only affect the target node, we present an LP-based exact algorithm. For the case when defending resources cannot be shared, we present a max-flow-based exact algorithm. We show that the general problem is NP-hard, and we give a 2-approximation algorithm based on LP-rounding. Moreover, by giving a matching lower bound of 2 on the integrality gap on the LP relaxation, we show that our rounding is tight., Comment: 16 pages, 3 figures, to appear in AAAI 2020

Classic dynamic data structure problems maintain a data structure subject to a sequence S of updates and they answer queries using the latest version of the data structure, i.e., the data structure after processing the whole sequence. To handle operations that change the sequence S of updates, Demaine et al. (TALG 2007) introduced retroactive data structures. A retroactive operation modifies the update sequence S in a given position t, called time, and either creates or cancels an update in S at time t. A partially retroactive data structure restricts queries to be executed exclusively in the latest version of the data structure. A fully retroactive data structure supports queries at any time t: a query at time t is answered using only the updates of S up to time t. If the sequence S only consists of insertions, the resulting data structure is an incremental retroactive data structure. While efficient retroactive data structures have been proposed for classic data structures, e.g., stack, priority queue and binary search tree, the retroactive version of graph problems are rarely studied. In this paper we study retroactive graph problems including connectivity, minimum spanning forest (MSF), maximum degree, etc. We provide fully retroactive data structures for maintaining the maximum degree, connectivity and MSF in $\tilde{O}(n)$ time per operation. We also give an algorithm for the incremental fully retroactive connectivity with $\tilde{O}(1)$ time per operation. We compliment our algorithms with almost tight hardness results. We show that under the OMv conjecture (proposed by Henzinger et al. (STOC 2015)), there does not exist fully retroactive data structures maintaining connectivity or MSF, or incremental fully retroactive data structure maintaining the maximum degree with $O(n^{1-\epsilon})$ time per operation, for any constant $\epsilon > 0$.

In the online load balancing problem on related machines, we have a set of jobs (with different sizes) arriving online, and we need to assign each job to a machine immediately upon its arrival, so as to minimize the makespan, i.e., the maximum completion time. In classic mechanism design problems, we assume that the jobs are controlled by selfish agents, with the sizes being their private information. Each job (agent) aims at minimizing its own cost, which is its completion time plus the payment charged by the mechanism. Truthful mechanisms guaranteeing that every job minimizes its cost by reporting its true size have been well-studied [Aspnes et al. JACM 1997, Feldman et al. EC 2017]. In this paper, we study truthful online load balancing mechanisms that are well-behaved [Epstein et al., MOR 2016]. Well-behavior is important as it guarantees fairness between machines, and implies truthfulness in some cases when machines are controlled by selfish agents. Unfortunately, existing truthful online load balancing mechanisms are not well-behaved. We first show that to guarantee producing a well-behaved schedule, any online algorithm (even non-truthful) has a competitive ratio at least $\Omega(\sqrt{m})$, where m is the number of machines. Then we propose a mechanism that guarantees truthfulness of the online jobs, and produces a schedule that is almost well-behaved. We show that our algorithm has a competitive ratio of $O(\log m)$. Moreover, for the case when the sizes of online jobs are bounded, the competitive ratio of our algorithm improves to $O(1)$. Interestingly, we show several cases for which our mechanism is actually truthful against selfish machines., Comment: A preliminary version appeared in AAMAS 2019

There has been a long history for studying randomized greedy matching algorithms since the work by Dyer and Frieze~(RSA 1991). We follow this trend and consider the problem formulated in the oblivious setting, in which the algorithm makes (random) decisions that are essentially oblivious to the input graph. We revisit the \textsf{Modified Randomized Greedy (MRG)} algorithm by Aronson et al.~(RSA 1995) that is proved to be $(0.5+\epsilon)$-approximate. In particular, we study a weaker version of the algorithm named \textsf{Random Decision Order (RDO)} that in each step, randomly picks an unmatched vertex and matches it to an arbitrary neighbor if exists. We prove the \textsf{RDO} algorithm is $0.639$-approximate and $0.531$-approximate for bipartite graphs and general graphs respectively. As a corollary, we substantially improve the approximation ratio of \textsf{MRG}. Furthermore, we generalize the \textsf{RDO} algorithm to the edge-weighted case and prove that it achieves a $0.501$ approximation ratio. This result solves the open question by Chan et al.~(SICOMP 2018) about the existence of an algorithm that beats greedy in this setting. As a corollary, it also solves the open questions by Gamlath et al.~(SODA 2019) in the stochastic setting., Comment: 30 pages. To appear in STOC 2020

In this paper, we investigate the performance of a class of spatially coupled codes, namely partially information coupled turbo codes (PIC-TCs) over the binary erasure channel (BEC). This class of codes enjoy flexible code rate adjustment by varying the coupling ratio. Moreover, the coupling method can be directly applied to any component codes without changing the encoding and decoding architectures of the underlying component codes. However, the theoretical performance of PIC-TCs has not been fully investigated. For this work, we consider the codes that have coupling memory $m$ and study the corresponding graph model. We then derive the exact density evolution equations for these code ensembles with any given coupling ratio and coupling memory $m$ to precisely compute their belief propagation decoding thresholds for the BEC. Our simulation results verify the correctness of our theoretical analysis and also show better error performance over uncoupled turbo codes with a variety of code rates on the BEC., Comment: 5 pages, 3 figures, accepted 2019 IEEE Information Theory Workshop (ITW)

We study envy-free allocations of indivisible goods to agents in settings where each agent is unaware of the goods allocated to other agents. In particular, we propose the maximin aware (MMA) fairness measure, which guarantees that every agent, given the bundle allocated to her, is aware that she does not envy at least one other agent, even if she does not know how the other goods are distributed among other agents. We also introduce two of its relaxations and discuss their egalitarian guarantee and existence. Finally, we present a polynomial-time algorithm, which computes an allocation that approximately satisfies MMA or its relaxations. Interestingly, the returned allocation is also 1/2 -approximate EFX when all agents have subadditive valuations, which improves the algorithm in [Plaut and Roughgarden, SODA 2018].

We initiate the work on fair and strategyproof allocation of indivisible chores. The fairness concept we consider in this paper is maxmin share (MMS) fairness. We consider three previously studied models of information elicited from the agents: the ordinal model, the cardinal model, and the public ranking model in which the ordinal preferences are publicly known. We present both positive and negative results on the level of MMS approximation that can be guaranteed if we require the algorithm to be strategyproof. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods.

Huang et al.~(STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive online and considers general graphs. They showed that the ranking algorithm by Karp et al.~(STOC 1990) is strictly better than $0.5$-competitive and the problem is strictly harder than the online bipartite matching problem in that no algorithms can be $(1-1/e)$-competitive. This paper pins down two tight competitive ratios of classic algorithms for the fully online matching problem. For the fractional version of the problem, we show that a natural instantiation of the water-filling algorithm is $2-\sqrt{2} \approx 0.585$-competitive, together with a matching hardness result. Interestingly, our hardness result applies to arbitrary algorithms in the edge-arrival models of the online matching problem, improving the state-of-art $\frac{1}{1+\ln 2} \approx 0.5906$ upper bound. For integral algorithms, we show a tight competitive ratio of $\approx 0.567$ for the ranking algorithm on bipartite graphs, matching a hardness result by Huang et al. (STOC 2018)., Comment: To appear SODA 2019

We consider the online makespan minimization problem on identical machines. Chen and Vestjens (ORL 1997) show that the largest processing time first (LPT) algorithm is 1.5-competitive. For the special case of two machines, Noga and Seiden (TCS 2001) introduce the SLEEPY algorithm that achieves a competitive ratio of $(5 - \sqrt{5})/2 \approx 1.382$, matching the lower bound by Chen and Vestjens (ORL 1997). Furthermore, Noga and Seiden note that in many applications one can kill a job and restart it later, and they leave an open problem whether algorithms with restart can obtain better competitive ratios. We resolve this long-standing open problem on the positive end. Our algorithm has a natural rule for killing a processing job: a newly-arrived job replaces the smallest processing job if 1) the new job is larger than other pending jobs, 2) the new job is much larger than the processing one, and 3) the processed portion is small relative to the size of the new job. With appropriate choice of parameters, we show that our algorithm improves the 1.5 competitive ratio for the general case, and the 1.382 competitive ratio for the two-machine case., Comment: 36 pages, 6 figures, to appear in APPROX 2018

We introduce a weighted version of the ranking algorithm by Karp et al. (STOC 1990), and prove a competitive ratio of 0.6534 for the vertex-weighted online bipartite matching problem when online vertices arrive in random order. Our result shows that random arrivals help beating the 1-1/e barrier even in the vertex-weighted case. We build on the randomized primal-dual framework by Devanur et al. (SODA 2013) and design a two dimensional gain sharing function, which depends not only on the rank of the offline vertex, but also on the arrival time of the online vertex. To our knowledge, this is the first competitive ratio strictly larger than 1-1/e for an online bipartite matching problem achieved under the randomized primal-dual framework. Our algorithm has a natural interpretation that offline vertices offer a larger portion of their weights to the online vertices as time goes by, and each online vertex matches the neighbor with the highest offer at its arrival., Comment: 15 pages, 2 figures, appeared in ICALP 2018 and TALG 2019

We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously-arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors' arrivals. If a vertex remains unmatched until its deadline, the algorithm must then irrevocably either match it to an unmatched neighbor, or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, etc. We show that the Ranking algorithm by Karp et al. (STOC 1990) is $0.5211$-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats $0.5$ on general graphs in an online matching problem, a first step towards solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is between $0.5541$ and $0.5671$. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be $0.6317 < 1-\frac{1}{e}$-competitive in our model even for bipartite graphs., Comment: 25 pages, 10 figures, to appear in STOC 2018

In spectral graph theory, the Cheeger's inequality gives upper and lower bounds of edge expansion in normal graphs in terms of the second eigenvalue of the graph's Laplacian operator. Recently this inequality has been extended to undirected hypergraphs and directed normal graphs via a non-linear operator associated with a diffusion process in the underlying graph. In this work, we develop a unifying framework for defining a diffusion operator on a directed hypergraph with stationary vertices, which is general enough for the following two applications. 1. Cheeger's inequality for directed hyperedge expansion. 2. Quadratic optimization with stationary vertices in the context of semi-supervised learning. Despite the crucial role of the diffusion process in spectral analysis, previous works have not formally established the existence of the corresponding diffusion processes. In this work, we give a proof framework that can indeed show that such diffusion processes are well-defined. In the first application, we use the spectral properties of the diffusion operator to achieve the Cheeger's inequality for directed hyperedge expansion. In the second application, the diffusion operator can be interpreted as giving a continuous analog to the subgradient method, which moves the feasible solution in discrete steps towards an optimal solution.

We propose a new class of information-coupled (IC) Turbo codes to improve the transport block (TB) error rate performance for long-term evolution (LTE) systems, while keeping the hybrid automatic repeat request protocol and the Turbo decoder for each code block (CB) unchanged. In the proposed codes, every two consecutive CBs in a TB are coupled together by sharing a few common information bits. We propose a feed-forward and feed-back decoding scheme and a windowed (WD) decoding scheme for decoding the whole TB by exploiting the coupled information between CBs. Both decoding schemes achieve a considerable signal-to-noise-ratio (SNR) gain compared to the LTE Turbo codes. We construct the extrinsic information transfer (EXIT) functions for the LTE Turbo codes and our proposed IC Turbo codes from the EXIT functions of underlying convolutional codes. An SNR gain upper bound of our proposed codes over the LTE Turbo codes is derived and calculated by the constructed EXIT charts. Numerical results show that the proposed codes achieve an SNR gain of 0.25 dB to 0.72 dB for various code parameters at a TB error rate level of $10^{-2}$, which complies with the derived SNR gain upper bound., Comment: 13 pages, 12 figures

We consider the online vector packing problem in which we have a $d$ dimensional knapsack and items $u$ with weight vectors $\mathbf{w}_u \in \mathbb{R}_+^d$ arrive online in an arbitrary order. Upon the arrival of an item, the algorithm must decide immediately whether to discard or accept the item into the knapsack. When item $u$ is accepted, $\mathbf{w}_u(i)$ units of capacity on dimension $i$ will be taken up, for each $i\in[d]$. To satisfy the knapsack constraint, an accepted item can be later disposed of with no cost, but discarded or disposed of items cannot be recovered. The objective is to maximize the utility of the accepted items $S$ at the end of the algorithm, which is given by $f(S)$ for some non-negative monotone submodular function $f$. For any small constant $\epsilon > 0$, we consider the special case that the weight of an item on every dimension is at most a $(1-\epsilon)$ fraction of the total capacity, and give a polynomial-time deterministic $O(\frac{k}{\epsilon^2})$-competitive algorithm for the problem, where $k$ is the (column) sparsity of the weight vectors. We also show several (almost) tight hardness results even when the algorithm is computationally unbounded. We show that under the $\epsilon$-slack assumption, no deterministic algorithm can obtain any $o(k)$ competitive ratio, and no randomized algorithm can obtain any $o(\frac{k}{\log k})$ competitive ratio. For the general case (when $\epsilon = 0$), no randomized algorithm can obtain any $o(k)$ competitive ratio. In contrast to the $(1+\delta)$ competitive ratio achieved in Kesselheim et al. (STOC 2014) for the problem with random arrival order of items and under large capacity assumption, we show that in the arbitrary arrival order case, even when $\| \mathbf{w}_u \|_\infty$ is arbitrarily small for all items $u$, it is impossible to achieve any $o(\frac{\log k}{\log\log k})$ competitive ratio., Comment: The conference version of this paper appears in ESA 2017

Two standing-wave single-cell choke-mode damped structures with different choke dimensions which worked at 11.424 GHz were designed, manufactured and tuned by accelerator group in Tsinghua University. High power test was carried out to study choke-mode structure's properties in high gradient and related breakdown phenomenon. A single-cell structure without choke which almost has the same inner dimension as choke-mode structure was also tested as a comparison to study how the choke affects high-gradient properties. In this paper, we report on the latest status of the high power test, including various observations and the experimental results., Comment: Talk presented at the International Workshop on Future Linear Colliders (LCWS2016), Morioka, Japan, 5-9 December 2016. C16-12-05.4

We study the max-min fair allocation problem in which a set of $m$ indivisible items are to be distributed among $n$ agents such that the minimum utility among all agents is maximized. In the restricted setting, the utility of each item $j$ on agent $i$ is either $0$ or some non-negative weight $w_j$. For this setting, Asadpour et al. showed that a certain configuration-LP can be used to estimate the optimal value within a factor of $4+\delta$, for any $\delta>0$, which was recently extended by Annamalai et al. to give a polynomial-time $13$-approximation algorithm for the problem. For hardness results, Bezakova and Dani showed that it is \NP-hard to approximate the problem within any ratio smaller than $2$. In this paper we consider the $(1,\epsilon)$-restricted max-min fair allocation problem in which each item $j$ is either heavy $(w_j = 1)$ or light $(w_j = \epsilon)$, for some parameter $\epsilon \in (0,1)$. We show that the $(1,\epsilon)$-restricted case is also \NP-hard to approximate within any ratio smaller than $2$. Hence, this simple special case is still algorithmically interesting. Using the configuration-LP, we are able to estimate the optimal value of the problem within a factor of $3+\delta$, for any $\delta>0$. Extending this idea, we also obtain a quasi-polynomial time $(3+4\epsilon)$-approximation algorithm and a polynomial time $9$-approximation algorithm. Moreover, we show that as $\epsilon$ tends to $0$, the approximation ratio of our polynomial-time algorithm approaches $3+2\sqrt{2}\approx 5.83$.

Motivated by online advertisement and exchange settings, greedy randomized algorithms for the maximum matching problem have been studied, in which the algorithm makes (random) decisions that are essentially oblivious to the input graph. Any greedy algorithm can achieve performance ratio 0.5, which is the expected number of matched nodes to the number of nodes in a maximum matching. Since Aronson, Dyer, Frieze and Suen proved that the Modified Randomized Greedy (MRG) algorithm achieves performance ratio 0.5 + \epsilon (where \epsilon = frac{1}{400000}) on arbitrary graphs in the mid-nineties, no further attempts in the literature have been made to improve this theoretical ratio for arbitrary graphs until two papers were published in FOCS 2012. Poloczek and Szegedy also analyzed the MRG algorithm to give ratio 0.5039, while Goel and Tripathi used experimental techniques to analyze the Ranking algorithm to give ratio 0.56. However, we could not reproduce the experimental results of Goel and Tripathi. In this paper, we revisit the Ranking algorithm using the LP framework. Special care is given to analyze the structural properties of the Ranking algorithm in order to derive the LP constraints, of which one known as the \emph{boundary} constraint requires totally new analysis and is crucial to the success of our LP. We use continuous LP relaxation to analyze the limiting behavior as the finite LP grows. Of particular interest are new duality and complementary slackness characterizations that can handle the monotone and the boundary constraints in continuous LP. We believe our work achieves the currently best theoretical performance ratio of \frac{2(5-\sqrt{7})}{9} \approx 0.523 on arbitrary graphs. Moreover, experiments suggest that Ranking cannot perform better than 0.724 in general., Comment: Corrected references in abstract