In the bottleneck multiple knapsack problem, we are given a set of items and a set of knapsacks, where each item has a profit and a weight, and each knapsack has a capacity. Our goal is to assign items to knapsacks so as to maximize the minimum profit received by any knapsack subject to the capacity constraint. When all knapsacks have identical capacity, we give a (2/3 - ε)-approximation algorithm for any constant ε > 0. This result almost matches the (2/3 + ε) inapproximability bound for the bottleneck multiple subset sum problem (Caprara et al., 2000). When the knapsacks can have arbitrary capacities, we propose a (1/2 - ε)-approximation algorithm for any constant ε > 0. We also prove a hardness bound of (1/2 + ε) for any constant ε > 0.

Existence of long arithmetic progressions in sumsets and subset sums is an important topic in additive combinatorics, and has applications in the design of algorithms for classic combinatorial optimization problems, including Subset Sum and Knapsack. Motivated by these applications, Chen, Mao and Zhang [STOC, 2025] studied arithmetic progressions from a computational perspective: instead of merely knowing the existence of arithmetic progressions, they aim to construct it explicitly and find out how its terms can be represented using integers from the corresponding set. They show that both can be done in near-linear time for long arithmetic progressions in \(kA\), the \(k\)-fold sum of an integer set \(A\), and \(\mathcal{S}(A)\), the set of all subset sums of \(A\), where \(A\) is a set of nonnegative integers and \(|A|\) is relatively large comparing to \(\max(A)\) (the largest element in \(A\)). They left as an open problem whether the same thing can be achieved for long arithmetic progressions in the sumset of different sets, i.e., \(A_1 + A_2 + \cdots + A_k\).

Solving a general integer program (IP) is NP-hard. The classic algorithm [Papadimitriou, J.ACM '81] for IPs has a running time n^{{𝒪}(m)}(m⋅max{Δ,‖b‖_{∞}})^{{𝒪}(m²)}, where m is the number of constraints, n is the number of variables, and Δ and ‖b‖_{∞} are, respectively, the largest absolute values among the entries in the constraint matrix and the right-hand side vector of the constraint. The running time is exponential in m, and becomes pseudo-polynomial if m is a constant. In recent years, there has been extensive research on FPT (fixed parameter tractable) algorithms for the so-called n-fold IPs, which may possess a large number of constraints, but the constraint matrix satisfies a specific block structure. It is remarkable that these FPT algorithms take as parameters Δ and the number of rows and columns of some small submatrices. If Δ is not treated as a parameter, then the running time becomes pseudo-polynomial even if all the other parameters are taken as constants. This paper explores the trade-off between time and accuracy in solving an IP. We show that, for arbitrary small ε > 0, there exists an algorithm for IPs with m constraints that runs in {f(m,ε)}⋅poly(|I|) time, and returns a near-feasible solution that violates the constraints by at most εΔ. Furthermore, for n-fold IPs, we establish a similar result - our algorithm runs in time that depends on the number of rows and columns of small submatrices together with 1/ε, and returns a solution that slightly violates the constraints. Meanwhile, both solutions guarantee that their objective values are no worse than the corresponding optimal objective values satisfying the constraints. As applications, our results can be used to obtain additive approximation schemes for multidimensional knapsack as well as scheduling.

We consider the classic Knapsack problem. Let $t$ and $\mathrm{OPT}$ be the capacity and the optimal value, respectively. If one seeks a solution with total profit at least $\mathrm{OPT}/(1 + \varepsilon)$ and total weight at most $t$, then Knapsack can be solved in $\tilde{O}(n + (\frac{1}{\varepsilon})^2)$ time [Chen, Lian, Mao, and Zhang '24][Mao '24]. This running time is the best possible (up to a logarithmic factor), assuming that $(\min,+)$-convolution cannot be solved in truly subquadratic time [Künnemann, Paturi, and Schneider '17][Cygan, Mucha, Węgrzycki, and Włodarczyk '19]. The same upper and lower bounds hold if one seeks a solution with total profit at least $\mathrm{OPT}$ and total weight at most $(1 + \varepsilon)t$. Therefore, it is natural to ask the following question. If one seeks a solution with total profit at least $\mathrm{OPT}/(1+\varepsilon)$ and total weight at most $(1 + \varepsilon)t$, can Knsapck be solved in $\tilde{O}(n + (\frac{1}{\varepsilon})^{2-δ})$ time for some constant $δ> 0$? We answer this open question affirmatively by proposing an $\tilde{O}(n + (\frac{1}{\varepsilon})^{7/4})$-time algorithm.

We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set$X$of$n$positive integers and a target$t$, Subset Sum asks whether some subset of$X$sums to$t$. Bringmann proposes an$\tilde{O}(n+t)$-time algorithm [Bringmann SODA'17], and an open question has naturally arisen: can Subset Sum be solved in$O(n+w)$time? Here$w$is the maximum integer in$X$. We make a progress towards resolving the open question by proposing an$\tilde{O}(n+\sqrt{wt})$-time algorithm.

We investigate pseudopolynomial-time algorithms for Bounded Knapsack and Bounded Subset Sum. Recent years have seen a growing interest in settling their fine-grained complexity with respect to various parameters. For Bounded Knapsack, the number of items n and the maximum item weight wmax are two of the most natural parameters that have been studied extensively in the literature. The previous best running time in terms of n and wmax is [Polak, Rohwedder, Węgrzycki ‘21]. There is a conditional lower bound of (n + wmax)2-o(1) based on (min, +)-convolution hypothesis [Cygan, Mucha, Węgrzycki, Włodarczyk ‘17]. We narrow the gap significantly by proposing an -time algorithm. Our algorithm works for both 0-1 Knapsack and Bounded Knapsack. Note that in the regime where wmax ≈ n, our algorithm runs in Õ(n12/5) time, while all the previous algorithms require Ω(n3) time in the worst case.

We investigate the classic Knapsack problem and propose a fully polynomial-time approximation scheme (FPTAS) that runs in O(n + (1/)2) time. Prior to our work, the best running time is O(n + (1/)11/5) [Deng, Jin, and Mao’23]. Our algorithm is the best possible (up to a polylogarithmic factor), as Knapsack has no O((n + 1/)2−δ)-time FPTAS for any constant δ > 0, conditioned on the conjecture that (min, +)-convolution has no truly subquadratic-time algorithm.

We propose an O(n + 1/)-time FPTAS (Fully Polynomial-Time Approximation Scheme) for the classical Partition problem. This is the best possible (up to a polylogarithmic factor) assuming SETH (Strong Exponential Time Hypothesis) [Abboud, Bringmann, Hermelin, and Shabtay’22]. Prior to our work, the best known FPTAS for Partition runs in O(n + 1/5/4) time [Deng, Jin and Mao’23, Wu and Chen’22]. Our result is obtained by solving a more general problem of weakly approximating Subset Sum.

Recent advances in blockchain research have been made in two important directions. One is refined resilience analysis utilizing game theory to study the consequences of selfish behavior of users (miners), and the other is the extension from a linear (chain) structure to a non-linear (graphical) structure for performance improvements, such as IOTA and Graphcoin. The first question that comes to mind is what improvements a blockchain system would see by leveraging these new advances. In this article, we consider three major properties for a blockchain system: α-partial verification, scalability, and finality-duration. We establish a formal framework and prove that no blockchain system can achieve α-partial verification for any fixed constant α, high scalability, and low finality-duration simultaneously. We observe that classical blockchain systems like Bitcoin achieve full verification (α =1) and low finality-duration, Ethereum 2.0 Sharding achieves low finality-duration and high scalability. We are interested in whether it is possible to partially satisfy the three properties.

With the recent advances in concepts like decentralized “cloud” and blockchain-enabled decentralized computing environments, the legacy modeling and orchestration tools developed to support centrally managed cloud-based ICT infrastructures are challenged by such a new paradigm built on top of decentralization. On the other hand, decentralized “cloud” and computing infrastructures need to support many Dapp use cases. As the complexity of these targeted application scenarios increases, there is an urgent need for developing automation and modeling tools for deploying and managing decentralized infrastructures. Instead of creating such tools from scratch, a natural approach is extending mature infrastructure modeling tools for Dapps and decentralized computing environments. To this end, in this work, we have developed extensions to the TOSCA domain-specific language to support smart contract specification of decentralized computing infrastructures for supporting Dapps, where smart contracts or chain codes manage a decentralized computing environment. The result is blockchain-based orchestration and automation for decentralized “cloud” and computing environments that use existing infrastructure as code tools to deploy and manage decentralized applications.

Trusted execution environment (TEE) technology has many uses, such as protecting data in the cloud and improving security for industrial IoT. However, there are technical challenges that limit its widespread adoption. These challenges include the fact that different TEE vendors have incompatible solutions, and devices equipped with the same TEE technology may belong to different owners, making it difficult to establish trust between them. To address these challenges and fully utilize TEE technology, a decentralized coordination mechanism called DHTee is proposed. DHTee uses blockchain technology to support key TEE functions in a heterogeneous TEE environment, especially attestation service. Devices equipped with TEE can interact securely with the blockchain to determine whether potential collaborating devices meet the requirements. DHTee is also flexible and can support new TEE schemes without affecting existing TEEs.

Function-as-a-service (FaaS) is an emerging computation architecture, which provides high scalability and flexibility. All the existing F aaS systems are owned and managed by a single cloud service provider. While this is not an issue for most existing enterprise applications, such character is not compatible with the decentralization principle of dApp/Web3 applications, more of which are being deployed in the cloud environment. Therefore, there is an urgent need to build a decentralized FaaS, which is managed by multiple cloud service providers and allows a decentralized application to take advantages of FaaS. In this research paper, we propose DeFaaS, a novel system for managing decentralized FaaS using blockchain technology and decentralized API management, where functions are executed on a distributed network of nodes by multi-cloud data centers, rather than on a centralized server. This allows for greater scalability and flexibility, as well as improved security and reliability.

We study a bilevel optimization problem which is a zero-sum Stackelberg game. In this problem, there are two players, a leader and a follower, who pick items from a common set. Both the leader and the follower have their own (multi-dimensional) budgets, respectively. Each item is associated with a profit, which is the same to the leader and the follower, and will consume the leader's (follower's) budget if it is selected by the leader (follower). The leader and the follower will select items in a sequential way: First, the leader selects items within the leader's budget. Then the follower selects items from the remaining items within the follower's budget. The goal of the leader is to minimize the maximum profit that the follower can obtain. Let $s_A$ and $s_B$ be the dimension of the leader's and follower's budget, respectively. A special case of our problem is the bilevel knapsack problem studied by Caprara et al. [SIAM Journal on Optimization, 2014], where $s_A=s_B=1$. We consider the general problem and obtain an $(s_B+ε)$-approximation algorithm when $s_A$ and $s_B$ are both constant. In particular, if $s_B=1$, our algorithm implies a PTAS for the bilevel knapsack problem, which is the first O(1)-approximation algorithm. We also complement our result by showing that there does not exist any $(4/3-ε)$-approximation algorithm even if $s_A=1$ and $s_B=2$. We also consider a variant of our problem with resource augmentation when $s_A$ and $s_B$ are both part of the input. We obtain an O(1)-approximation algorithm with O(1)-resource augmentation, that is, we give an algorithm that returns a solution which exceeds the given leader's budget by O(1) times, and the objective value achieved by the solution is O(1) times the optimal objective value that respects the leader's budget.

With the recent advance in concepts like decentralized "cloud" and blockchain-enabled decentralized computing environments, the legacy modeling and orchestration tools developed to support centrally managed cloud-based ICT infrastructures are challenged by such a new paradigm built on top of decentralization. On the other hand, decentralized "cloud" and computing infrastructures need to support many Dapp use cases. As the complexity of these targeted application scenarios increases, there is an urgent need for developing automation and modeling tools for deploying and managing decentralized infrastructures. Instead of creating such tools from scratch, a natural approach is extending mature infrastructure modeling tools for Dapps and decentralized computing environments. To this end, in this work, we have developed extensions to the TOSCA domain-specific language to support smart contract specification of decentralized computing infrastructures for supporting Dapps, where smart contracts or chain codes manage a decentralized computing environment. The result is blockchain-based orchestration and automation for decentralized "cloud" and computing environments, which is a step forward for achieving full decentralization in general-purpose computing.

The resilience of a voting system has been a central topic in computational social choice. Many voting rules, like plurality, are shown to be vulnerable as the attacker can target specific voters to manipulate the result. What if a local differential privacy (LDP) mechanism is adopted such that the true preference of a voter is never revealed in pre-election polls? In this case, the attacker can only infer stochastic information about a voter's true preference, and this may cause the manipulation of the electoral result significantly harder. The goal of this paper is to provide a quantitative study on the effect of adopting LDP mechanisms on a voting system. We introduce the metric PoLDP (power of LDP) that quantitatively measures the difference between the attacker's manipulation cost under LDP mechanisms and that without LDP mechanisms. The larger PoLDP is, the more robustness LDP mechanisms can add to a voting system. We give a full characterization of PoLDP for the voting system with plurality rule and provide general guidance towards the application of LDP mechanisms.

We consider a classical scheduling problem on m identical machines. For an arbitrary constant q > 1, the aim is to assign jobs to machines such that is minimized, where Ci is the total processing time of jobs assigned to machine i. It is well known that this problem is strongly NP-hard. Under mild assumptions, the running time of an (1 + ∊)-approximation algorithm for a strongly NP-hard problem cannot be polynomial on 1/∊, unless P = NP. For most problems in the literature, this translates into algorithms with running time at least as large as 2Ω(1/∊) + nO(1). For the natural scheduling problem above, we establish the existence of an algorithm which violates this threshold. More precisely, we design a PTAS that runs in time. This result is in sharp contrast to the closely related minimum makespan variant, where an exponential lower bound is known under the exponential time hypothesis (ETH). We complement our result with an essentially matching lower bound on the running time, showing that our algorithm is best-possible under ETH. The lower bound proof exploits new number-theoretical constructions for variants of progression-free sets, which might be of independent interest. Furthermore, we provide a fine-grained characterization on the running time of a PTAS for this problem depending on the relation between ∊ and the number of machines m. More precisely, our lower bound only holds when . Better algorithms, that go beyond the lower bound, exist for other values of m. In particular, there even exists an algorithm with running time polynomial in 1/∊ if we restrict ourselves to instances with m = Ω(1/∊ log2 1/∊).

In this paper, we present the design and implementation of a privacy preserving event based UTXO (Unspent Transaction Output) transaction system. Unlike the existing approaches that often depend on smart contracts where digital assets are first locked in a vault, and then released according to event triggers, the event based transaction system encodes event outcome as part of the UTXO note and safeguards event privacy by shielding it with zero-knowledge proof based protocols such that associations between UTXO notes and events are hidden from the validators. Without relying on any triggering mechanism, the proposed transaction system separates event processing from the transaction processing where confidential event based UTXO notes (event based UTXOs or conditional UTXOs) can be transferred freely with full privacy in an asynchronous manner, only with their asset values conditional to the linked event outcomes. The main advantage of such design is that it enables free trade of event based digital assets and prevents the assets from being locked. We implemented the proposed transaction system by extending the Zerocoin data model and protocols. The system is implemented and evaluated using xJsnark.

Iterative augmentation has recently emerged as an overarching method for solving Integer Programs (IP) in variable dimension, in stark contrast with the volume and flatness techniques of IP in fixed dimension. Here we consider 4-block n-fold integer programs, which are the most general class considered so far. A 4-block n-fold IP has a constraint matrix which consists of n copies of small matrices A, B, and D, and one copy of C, in a specific block structure. Iterative augmentation methods rely on the so-called Graver basis of the constraint matrix, which constitutes a set of fundamental augmenting steps. All existing algorithms rely on bounding the 𝓁₁- or 𝓁_∞-norm of elements of the Graver basis. Hemmecke et al. [Math. Prog. 2014] showed that 4-block n-fold IP has Graver elements of 𝓁_∞-norm at most 𝒪_FPT(n^{2^{s_D}}), leading to an algorithm with a similar runtime; here, s_D is the number of rows of matrix D and 𝒪_FPT hides a multiplicative factor that is only dependent on the small matrices A,B,C,D, However, it remained open whether their bounds are tight, in particular, whether they could be improved to 𝒪_FPT(1), perhaps at least in some restricted cases. We prove that the 𝓁_∞-norm of the Graver elements of 4-block n-fold IP is upper bounded by 𝒪_FPT(n^{s_D}), improving significantly over the previous bound 𝒪_FPT(n^{2^{s_D}}). We also provide a matching lower bound of Ω(n^{s_D}) which even holds for arbitrary non-zero lattice elements, ruling out augmenting algorithm relying on even more restricted notions of augmentation than the Graver basis. We then consider a special case of 4-block n-fold in which C is a zero matrix, called 3-block n-fold IP. We show that while the 𝓁_∞-norm of its Graver elements is Ω(n^{s_D}), there exists a different decomposition into lattice elements whose 𝓁_∞-norm is bounded by 𝒪_FPT(1), which allows us to provide improved upper bounds on the 𝓁_∞-norm of Graver elements for 3-block n-fold IP. The key difference between the respective decompositions is that a Graver basis guarantees a sign-compatible decomposition; this property is critical in applications because it guarantees each step of the decomposition to be feasible. Consequently, our improved upper bounds let us establish faster algorithms for 3-block n-fold IP and 4-block IP, and our lower bounds strongly hint at parameterized hardness of 4-block and even 3-block n-fold IP. Furthermore, we show that 3-block n-fold IP is without loss of generality in the sense that 4-block n-fold IP can be solved in FPT oracle time by taking an algorithm for 3-block n-fold IP as an oracle.

Industrial IoT (IIoT) is critical for industrial infrastructure modernization and digitalization. Therefore, it is of utmost importance to provide adequate protection of the IIoT system. A modern IIoT system usually consists of a large number of devices that are deployed in multiple locations and owned/managed by different entities who do not fully trust each other. These features make it harder to manage the system in a coherent manner and utilize existing security mechanisms to offer adequate protection. The emerging blockchain technology provides a powerful tool for IIoT system management and protection because the IIoT nature of distributed deployment and involvement of multiple stakeholders fits the design philosophy of blockchain well. Most existing blockchain construction mechanisms are not scalable enough and too heavy for an IIoT system. One promising way to overcome these limitations is utilizing hardware based trusted execution environment (TEE) in blockchain construction. However, most of the existing works on this direction do not consider the characteristics of IIoT devices (e.g., fixed functionality and limited supply) and face several limitations when they are applied for IIoT system management and protection, such as high energy consumption, single root-of-trust, and low decentralization level. To mitigate these challenges, we propose a novel field programmable gate array (FPGA) based blockchain system. It leverages the FPGA to build a simple but efficient TEE for IIoT devices, and removes the single root-of-trust by allowing all stakeholders to participate in the management of the devices. The FPGA based blockchain system shifts the computation/storage intensive part of blockchain management to more powerful computers but still involves the IIoT devices in the block construction to achieve a high level of decentralization. We implement the major FPGA components of the design and evaluate the performance of the whole system with a simulation tool to demonstrate its feasibility for IIoT applications.

IoT devices provide a rich data source that is not available in the past, which is valuable for a wide range of intelligence applications, especially deep neural network (DNN) applications that are data-thirsty. An established DNN model provides useful analysis results that can improve the operation of IoT systems in turn. The progress in distributed/federated DNN training further unleashes the potential of integration of IoT and intelligence applications. When a large number of IoT devices are deployed in different physical locations, distributed training allows training modules to be deployed to multiple edge data centers that are close to the IoT devices to reduce the latency and movement of large amounts of data. In practice, these IoT devices and edge data centers are usually owned and managed by different parties, who do not fully trust each other or have conflicting interests. It is hard to coordinate them to provide end-to-end integrity protection of the DNN construction and application with classical security enhancement tools. For example, one party may share an incomplete data set with others, or contribute a modified sub DNN model to manipulate the aggregated model and affect the decision-making process. To mitigate this risk, we propose a novel blockchain based end-to-end integrity protection scheme for DNN applications integrated with an IoT system in the edge computing environment. The protection system leverages a set of cryptography primitives to build a blockchain adapted for edge computing that is scalable to handle a large number of IoT devices. The customized blockchain is integrated with a distributed/federated DNN to offer integrity and authenticity protection services.

Bribery in election (or computational social choice in general) is an important problem that has received a considerable amount of attention. In the classic bribery problem, the briber (or attacker) bribes some voters in attempting to make the briber’s designated candidate win an election. In this paper, we introduce a novel variant of the bribery problem, “Election with Bribed Voter Uncertainty” or BVU for short, accommodating the uncertainty that the vote of a bribed voter may or may not be counted. This uncertainty occurs either because a bribed voter may not cast its vote in fear of being caught, or because a bribed voter is indeed caught and therefore its vote is discarded. As a first step towards ultimately understanding and addressing this important problem, we show that it does not admit any multiplicative O(1)-approximation algorithm modulo standard complexity assumptions. We further show that there is an approximation algorithm that returns a solution with an additive-ε error in FPT time for any fixed ε.

Researchers deal with the class imbalanced problem in many real-world applications and GAN based data augmentation is considered as an efficient approach to address this problem. GANs need a huge training data to generate efficient augmented data. However, the required sufficient training data is not available in many research areas. In this paper, we introduce a new concept called virtual big data to address this problem. We prove that, virtual big data can provide the GANs sufficient training data to generate efficient augmented data with less mode collapse and vanishing generator gradients problems. We show that, the curse of dimensionality which is considered as a negative factor in machine learning can play a positive role to solve vanishing generator gradients via making discriminator less perfect. First, we transform the training data from n dimensional space into m dimensional space where, m = c * n and c is concatenation factor. To do so, c different training instances are selected and concatenated to each other to form a c * n dimensional instance. Increasing the dimension of training data from n to c * n is key to increase the number of training instances from N to C(N, c). Transformed training data are called virtual big data since they differ original training instances in terms of size and dimension. Our experiments show that, V-GAN, a GAN trained by virtual big data can outperform standard GANs when it comes to deal with extremely scarce training data. Furthermore, V-GAN can outperform traditional oversampling techniques in terms of precision, F1 score and Area Under Curve (AUC) score.

We consider the electoral bribery problem in computational social choice. In this context, extensive studies have been carried out to analyze the computational vulnerability of various voting (or election) rules. However, essentially all prior studies assume a deterministic model where each voter has an associated threshold value, which is used as follows. A voter will take a bribe and vote according to the attacker's (i.e., briber's) preference when the amount of the bribe is above the threshold, and a voter will not take a bribe when the amount of the bribe is not above the threshold (in this case, the voter will vote according to its own preference, rather than the attacker's). In this paper, we initiate the study of a more realistic model where each voter is associated with a willingness function, rather than a fixed threshold value. The willingness function characterizes the likelihood a bribed voter would vote according to the attacker's preference; we call this bribe-effect uncertainty. We characterize the computational complexity of the electoral bribery problem in this new model. In particular, we discover a dichotomy result: a certain mathematical property of the willingness function dictates whether or not the computational hardness can serve as a deterrence to bribery attackers.

We study the scheduling problem with calibrations. In 2013, Bender et al. (SPAA '13) proposed a theoretical framework for the problem. Jobs of unit processing time with release times and deadlines are to be scheduled on parallel identical machines. The machines need to be calibrated to run jobs while a single calibration remains valid on a machine only for a time period of length T. The objective is to find a schedule that completes all jobs within their timing constraints and minimizes the total number of calibrations. In this paper, we aim to design an approximation algorithm to solve the problem. We propose a dynamic programming algorithm with polynomial running time when the number of machines is constant. In addition, we give a PTAS when the number of machines is input.

We consider the multiple traveling salesman problem on a weighted tree. In this problem there are m salesmen located at the root initially. Each of them will visit a subset of vertices and return to the root. The goal is to assign a tour to every salesman such that every vertex is visited and the longest tour among all salesmen is minimized. The problem is equivalent to the subtree cover problem, in which we cover a tree with rooted subtrees such that the weight of the maximum weighted subtree is minimized. The classical machine scheduling problem can be viewed as a special case of our problem when the given tree is a star. We provide approximation and parameterized algorithms for this problem. We first present a PTAS (Polynomial Time Approximation Scheme). We then observe that, the problem remains NP-hard even if tree height and edge weight are constant, and present an FPT algorithm for this problem parameterized by the largest tour length. To achieve the FPT algorithm, we first formulate the problem as an integer linear program having a certain “tree-fold” structure. Then we show that an ILP with such a structure is FPT, which is a generalization of an earlier FPT result for n-fold integer programming by Hemmecke, Onn and Romanchuk [5]. This extension of n-fold ILP may be of independent interest.

We consider the online machine minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on a minimum number of machines. Our main result is a general $\mathcal{O}(\log {m})$-competitive algorithm for the online problem, where $m$ is the optimal number of machines used in an offline solution. This is the first improvement to an intriguing problem in nearly two decades. To date, the best known result is a $\mathcal{O}(\log (p_{\max}/p_{\min}))$-competitive algorithm by Phillips et al. [ Optimal time-critical scheduling via resource augmentation, STOC, 1997] that depends on the ratio of maximum and minimum job sizes, $p_{\max}$ and $p_{\min}$. Even for $m=2$ no better algorithm was known. Our algorithm is in this case constant-competitive. When applied to laminar or agreeable instances, our algorithm achieves a competitive ratio of $\mathcal{O}(1)$ even independently of $m$. The following two key components lead to our new result. First, we derive a new lower bound on the optimum value that relates the laxity and the number of jobs with intersecting time windows. Then, we design a new algorithm that is tailored to this lower bound and balances the delay of jobs by taking the number of currently running jobs into account.

We consider a natural generalization of the classical multiple knapsack problem in which instead of packing single items we are packing groups of items. In this problem, we have multiple knapsacks and a set of items partitioned into groups. Each item has an individual weight, while the profit is associated with groups rather than items. The profit of a group can be attained if and only if every item of this group is packed. Such a general model finds applications in various practical problems, e.g., delivering bundles of goods. The tractability of this problem relies heavily on how large a group could be. Deciding if a group of items of total weight 2 could be packed into two knapsacks of unit capacity is already NP -hard and it thus rules out a constant-approximation algorithm for this problem in general. We then focus on the parameterized version where the total weight of items in each group is bounded by a factor δ of the total capacity of all knapsacks. Both approximation and inapproximability results with respect to δ are derived. We also show that, depending on whether the number of knapsacks is a constant or part of the input, the approximation ratio for the problem, as a function on δ, changes substantially, which has a clear difference from the classical multiple knapsack problem.

Modern supply chain is a complex system and plays an important role for different sectors under the globalization economic integration background. Supply chain management system is proposed to handle the increasing complexity and improve the efficiency of flows of goods. It is also useful to prevent potential frauds and guarantee trade compliance. Currently, most companies maintain their own IT system for supply chain management. However, this approach has some limitations that prevent one to get most of the supply chain information. Using emerging decentralized ledger technology to build supply chain management system is a promising direction. However, decentralized ledger usually suffers from low performance and lack of capability to protect information stored on the ledger. To overcome these challenges, we propose CoC, a novel supply chain management system based on hybrid decentralized ledger. We develop an efficient block construction method with the model and security mechanism to prevent unauthorized access to data stored on the ledger.

Blockchain, or distributed ledger, provides a way to build various decentralized systems without relying on any single trusted party. This is especially attractive for smart contracts, that different parties do not need to trust each other to have a contract, and the distributed ledger can guarantee correct execution of the contract. Most existing distributed ledger based smart contract systems process smart contracts in a serial manner, i.e., all users have to run a contract before its result can be accepted by the system. Although this approach is easy to implement and manage, it is not scalable and greatly limits the system's capability of handling a large number of smart contracts. In order to address this problem, we propose a scalable smart contract execution scheme that can run multiple smart contract in parallel to improve throughput of the system. Our scheme relies on two key techniques: a fair contract partition algorithm leveraging integer linear programming to partition a set of smart contracts into multiple subsets, and a random assignment protocol assigning subsets randomly to a subgroup of users. We prove that, our scheme is secure as long as more than 50% of the computational power is possessed by honest nodes. We then conduct experiments with data from existing smart contract system to evaluate the efficiency of our scheme. The results demonstrate that our approach is scalable and much more efficient than the existing smart contract platform.

Transaction system build on top of blockchain, especially smart contract, is becoming an important part of world economy. However, there is a lack of formal study on the behavior of users in these systems, which leaves the correctness and security of such system without a solid foundation. Unlike mining, in which the reward for mining a block is fixed, different execution results of a smart contract may lead to significantly different payoffs of users, which gives more incentives for some user to follow a branch that contains a wrong result, even if the branch is shorter. It is thus important to understand the exact probability that a branch is being selected by the system. We formulate this problem as the (+-)-Biased Ballot Problem as follows: there are n voters one by one voting for either of the two candidates A and B. The probability of a user voting for A or B depends on whether the difference between the current votes of A and B is positive or negative. Our model takes into account the behavior of three different kinds of users when a branch occurs in the system -- users having preference over a certain branch based on the history of their transactions, and users being indifferent and simply follow the longest chain. We study two important probabilities that are closely related with a blockchain based system - the probability that A wins at last, and the probability that A receives d votes first. We show how to recursively calculate the two probabilities for any fixed n and d, and also discuss their asymptotic values when n and d are sufficiently large.

We study approximation and parameterized algorithms for R||C_max, focusing on the problem when the rank of the matrix formed by job processing times is small. Bhaskara et al. initiated the study of approximation algorithms with respect to the rank, showing that R||C_max admits a QPTAS (Quasi-polynomial time approximation scheme) when the rank is 2, and becomes APX-hard when the rank is 4. We continue this line of research. We prove that R||C_max is APX-hard even if the rank is 3, resolving an open problem. We then show that R||C_max is FPT parameterized by the rank and the largest job processing time p_max. This generalizes the parameterized results on P||C_max and R||C_max with few different types of machines. We also provide nearly tight lower bounds under Exponential Time Hypothesis which suggests that the running time of the FPT algorithm is unlikely to be improved significantly.

We consider the problem of scheduling with renewable speed-up resources. Given m identical machines, n jobs and c different discrete resources, the task is to schedule each job non-preemptively onto one of the machines so as to minimize the makespan. In our problem, a job has its original processing time, which could be reduced by utilizing one of the resources. As resources are different, the amount of the time reduced for each job is different depending on the resource it uses. Once a resource is being used by one job, it can not be used simultaneously by any other job until this job is finished, hence the scheduler should take into account the job-to-machine assignment together with the resource-to-job assignment. We observe that, the classical unrelated machine scheduling problem is actually a special case of our problem when m=c, i.e., the number of resources equals the number of machines. Extending the techniques for the unrelated machine scheduling, we give a 2-approximation algorithm when both m and c are part of the input. We then consider two special cases for the problem, with m or c being a constant, and derive PTASes (Polynomial Time Approximation Schemes) respectively. We also establish the relationship between the two parameters m and c, through which we are able to transform the PTAS for the case when m is constant to the case when c is a constant. The relationship between the two parameters reveals the structure within the problem, and may be of independent interest.

We consider the online machine minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on a minimum number of machines. Our main result is a general ℴ(log m)-competitive algorithm for the online problem, where m is the optimal number of machines used in an offline solution. This is the first improvement on an intriguing problem in nearly two decades. To date, the best known result is a ℴ(log(pmax/pmin))-competitive algorithm by Phillips et al. (STOC 1997) that depends on the ratio of maximum and minimum job sizes, pmax and pmin. Even for m = 2 no better algorithm was known. Our algorithm is in this case constant-competitive. When applied to laminar or agreeable instances, our algorithm achieves a competitive ratio of ℴ(1) even independently of m. The following two key components lead to our new result. Firstly, we derive a new lower bound on the optimum value that relates the laxity and the number of jobs with intersecting time windows. Then, we design a new algorithm that is tailored to this lower bound and balances the delay of jobs by taking the number of currently running jobs into account.

In this paper we investigate the power of migration in online scheduling on multiple parallel machines. The problem is to schedule preemptable jobs with release dates and deadlines on a minimum number of machines. We show that migration, that is, allowing that a preempted job is continued on a different machine, has a huge impact on the performance of a schedule. More precisely, let m be the number of machines required by a migratory solution; then the increase in the number of machines when disallowing migration is unbounded in m. This complements and strongly contrasts previous results on variants of this problem. In both the offline variant and a model allowing extra speed, the power of migration is limited as the increase of number of machines and speed, respectively, can be bounded by a small constant.

We consider a natural generalization of the classical multiple knapsack problem in which instead of packing single items we are packing groups of items. In this problem, we have multiple knapsacks and a set of items which are partitioned into groups. Each item has an individual weight, while the profit is associated with groups rather than items. The profit of a group can be attained if and only if every item of this group is packed. Such a general model finds applications in various practical problems, e.g., delivering bundles of goods. The tractability of this problem relies heavily on how large a group could be. Deciding if a group of items of total weight 2 could be packed into two knapsacks of unit capacity is already NP-hard and it thus rules out a constant-approximation algorithm for this problem in general. We then focus on the parameterized version where the total weight of items in each group is bounded by a factor delta of the total capacity of all knapsacks. Both approximation and inapproximability results with respect to delta are derived. We also show that, depending on whether the number of knapsacks is a constant or part of the input, the approximation ratio for the problem, as a function on delta, changes substantially, which has a clear difference from the classical multiple knapsack problem.

Users of cloud computing services are offered rapid access to computing resources via the Internet. Cloud providers use different pricing options such as (i) time slot reservation in advance at a fixed price and (ii) on-demand service at a (hourly) pay-as-used basis. Choosing the best combination of pricing options is a challenging task for users, in particular, when the instantiation of computing jobs underlies uncertainty. We propose a natural model for two-stage scheduling under uncertainty that captures such resource provisioning and scheduling problem in the cloud. Reserving a time unit for processing jobs incurs some cost, which depends on when the reservation is made: a priori decisions, based only on distributional information, are much cheaper than on-demand decisions when the actual scenario is known. We consider both stochastic and robust versions of scheduling unrelated machines with objectives of minimizing the sum of weighted completion times and the makespan. Our main contribution is an (8+eps)-approximation algorithm for the min-sum objective for the stochastic polynomial-scenario model. The same technique gives a (7.11+eps)-approximation for minimizing the makespan. The key ingredient is an LP-based separation of jobs and time slots to be considered in either the first or the second stage only, and then approximately solving the separated problems. At the expense of another epsilon our results hold for any arbitrary scenario distribution given by means of a black-box. Our techniques also yield approximation algorithms for robust two-stage scheduling.

We consider the classical scheduling problem on parallel identical machines to minimize the makespan. There is a long history of studies on this problem, focusing on exact and approximation algorithms, and it is thus natural to consider whether these algorithms are best possible in terms of the running time. Under the Exponential Time Hypothesis (ETH), we achieve the following results in this paper: The scheduling problem on a constant number m of identical machines, which is denoted as Pm‖Cmax, is known to admit a fully polynomial time approximation scheme (FPTAS) of running time O(n) + (1/∊)O(m) (indeed, the algorithm works for an even more general problem where machines are unrelated). We prove this algorithm is essentially the best possible in the sense that a (1/∊)O(m1–5) + nO(1) time FPTAS for any δ > 0 implies that ETH fails. The scheduling problem on an arbitrary number of identical machines, which is denoted as P‖Cmax, is known to admit a polynomial time approximation scheme (PTAS) of running time 2O(1/∊2log3(1/∊)) + nO(1). We prove this algorithm is nearly optimal in the sense that a 2O((1/∊)1–5) + nO(1) time PTAS for any δ > 0 implies that ETH fails, leaving a small room for improvement. In addition, we also consider exact algorithms for the scheduling problem and prove the following result: The traditional dynamic programming algorithm for P‖Cmax is known to run in 2O(n) time. We prove this is essentially the best possible in the sense that even if we restrict that there are n jobs and the processing time of each job is bounded by O(n), an exact algorithm of running time 2(n1–5) for any δ > 0 implies that ETH fails. To obtain these results we will provide two new reductions from 3SAT, one for P‖Cmax and another for P‖Cmax. Indeed, the new reductions explore the structure of scheduling problems and can also lead to other interesting results. For example, using the framework of our reduction for P‖Cmax, Chen et al. [5] are able to prove the APX-hardness of the scheduling problem in which the matrix of job processing times P = (pij)m×n is of rank 3, solving the open problem mentioned in [2].