Fair division is a fundamental problem in various multi-agent settings, where the goal is to divide a set of resources among agents in a fair manner. We study the case where m indivisible items need ...to be divided among n agents with additive valuations using the popular fairness notion of maximin share (MMS). An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist 1,2, a series of remarkable work 1,3–6 provided approximation algorithms for a 23-MMS allocation in which each agent receives a bundle worth at least 23 times her maximin share. More recently, Ghodsi et al. 7 showed the existence of a 34-MMS allocation and a PTAS to find a (34−ϵ)-MMS allocation for an ϵ>0. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain.
In this paper, we develop a new approach that gives a simple algorithm for showing the existence of a 34-MMS allocation. Furthermore, our approach is powerful enough to be easily extended in two directions: First, we get a strongly polynomial time algorithm to find a 34-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that there always exists a (34+112n)-MMS allocation, improving the best previous factor. This improves the approximation guarantee, most notably for small n. We note that 34 was the best factor known for n>4.
A non-empty subset S of the vertices of a digraph D is a safe set if
(i) for every strongly connected component M of D−S, there exists a strongly connected component N of DS such that there exists an ...arc from M to N; and
(ii) for every strongly connected component M of D−S and every strongly connected component N of DS, we have |M|≤|N| whenever there exists an arc from M to N.
In the case of acyclic digraphs a set X of vertices is a safe set precisely when X is an in-dominating set, that is, every vertex not in X has at least one arc to X. We prove that, even for acyclic digraphs which are traceable (have a hamiltonian path) it is NP-hard to find a minimum cardinality safe (in-dominating) set. Then we show that the problem is also NP-hard for tournaments and give, for every positive constant c, a polynomial algorithm for finding a minimum cardinality safe set in a tournament on n vertices in which no strong component has size more than clog(n). Under the so called Exponential Time Hypothesis (ETH) this is close to best possible in the following sense: If ETH holds, then, for every ϵ>0 there is no polynomial time algorithm for finding a minimum cardinality safe set for the class of tournaments in which the largest strong component has size at most log1+ϵ(n). We also discuss bounds on the cardinality of safe sets in tournaments.
Corrupted data appears widely in many contemporary applications including voting behavior, high-throughput sequencing and sensor networks. In this article, we consider the sparse modeling via L
0
...-regularization under the framework of high-dimensional measurement error models. By utilizing the techniques of the nearest positive semi-definite matrix projection, the resulting regularization problem can be efficiently solved through a polynomial algorithm. Under some interpretable conditions, we prove that the proposed estimator can enjoy comprehensive statistical properties including the model selection consistency and the oracle inequalities. In particular, the nonoptimality of the logarithmic factor of dimensionality will be showed in the oracle inequalities. We demonstrate the effectiveness of the proposed method by simulation studies.
•For given integers d, k and graph G, can we obtain a graph with diameter d via at most k edge deletions?•We determine the computational complexity of this and related problems for different values ...of d.•For d=3, the problem is related to Moore graphs and solvable in polynomial time.•For all d>4, the problem is NP-complete.•The NP-completeness results are proved for various values of the diameter of the input graph.
We study the following problem: for given integers d,k and graph G, can we obtain a graph with diameter d via at most k edge deletions? We determine the computational complexity of this and related problems for different values of d.
•The fractional governing equations of three variable section viscoelastic arches are established based on two fractional viscoelastic constitutive models.•Numerical solutions of displacement, stress ...and strain are obtained directly in the time domain by shifted Chebyshev polynomial algorithm.•Convergence analysis and error estimation prove the high accuracy and efficiency of proposed algorithm.•Performance testing for variable-section arches with different viscoelastic materials.
In this paper, two fractional viscoelastic constitutive models are used to establish nonlinear fractional integro-differential governing equations of variable-section viscoelastic arches. Shifted Chebyshev polynomial algorithm is introduced to numerically solve the governing equations directly in time domain. The feasibility and accuracy of the proposed algorithm are verified by convergence analysis and error estimation of a mathematical example. In addition, the dynamic responses of variable-section viscoelastic arches with three materials under two fractional models are also studied to verify the effectiveness of shifted Chebyshev polynomial algorithm.
Integer-valued elements of an integral submodular flow polyhedron Q are investigated which are decreasingly minimal (dec-min) in the sense that their largest component is as small as possible, within ...this, the second largest component is as small as possible, and so on. As a main result, we prove that the set of dec-min integral elements of Q is the set of integral elements of another integral submodular flow polyhedron arising from Q by intersecting a face of Q with a box. Based on this description, we develop a strongly polynomial algorithm for computing not only a dec-min integer-valued submodular flow but even a cheapest one with respect to a linear cost-function. A special case is the problem of finding a strongly connected (or k-edge-connected) orientation of a mixed graph whose in-degree vector is decreasingly minimal.
The current best practice in survivable routing is to compute link or node disjoint paths in the network topology graph. It can protect single-point failures; however, several failure events may ...cause the interruption of multiple network elements. The set of network elements subject to potential failure events is called Shared Risk Link Group (SRLG), identified during network planning. Unfortunately, for any given list of SRLGs, finding two paths that can survive a single SRLG failure is NP-Complete. In this paper, we provide a polynomial-time SRLG-disjoint routing algorithm for planar network topologies and a large set of SRLGs. Namely, we focus on regional failures, where the failed network elements must not be far from each other. We use a flexible definition of regional failure, where the only restrictions are that i) the topology is a planar graph, ii) each SRLG forms a set of connected edges in the dual of the planar graph, and iii) for each node <inline-formula> <tex-math notation="LaTeX">v</tex-math> </inline-formula>, the links incident to <inline-formula> <tex-math notation="LaTeX">v</tex-math> </inline-formula> are part of an SRLG. The proposed algorithm is based on a max-min theorem. Through extensive simulations, we show that the algorithm scales well with the network size, and one of the paths returned by the algorithm is only <inline-formula> <tex-math notation="LaTeX">4</tex-math> </inline-formula>% longer than the shortest path on average.
Contaminant oligonucleotide sequences such as primers and adapters can occur in both ends of high-throughput sequencing (HTS) reads. AlienTrimmer was developed in order to detect and remove such ...contaminants. Based on the decomposition of specified alien nucleotide sequences into k-mers, AlienTrimmer is able to determine whether such alien k-mers are occurring in one or in both read ends by using a simple polynomial algorithm. Therefore, AlienTrimmer can process typical HTS single- or paired-end files with millions of reads in several minutes with very low computer resources. Based on the analysis of both simulated and real-case Illumina®, 454™ and Ion Torrent™ read data, we show that AlienTrimmer performs with excellent accuracy and speed in comparison with other trimming tools. The program is freely available at ftp://ftp.pasteur.fr/pub/gensoft/projects/AlienTrimmer/.
•Removal of alien sequences (adapters, primers) from raw reads improves the quality of results from downstream analyses.•AlienTrimmer allows detecting and removing multiple alien sequences in both ends of sequence reads.•AlienTrimmer performs accurately and has fast running time.
The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We study complexity of the problem on hereditary subclasses of ...subcubic graphs. Each such subclass can be described by means of forbidden induced subgraphs. In case of finitely many forbidden induced subgraphs a necessary condition for polynomial-time solvability of the problem in subcubic graphs (unless P=NP) is the exclusion of the graph Si,j,k, which is a tree with three leaves of distance i,j,k from the only vertex of degree 3. Whether this condition is also sufficient is an open question, which was previously answered only for S1,k,k-free subcubic graphs and S2,2,2-free subcubic graphs. Combining various algorithmic techniques, in the present paper we generalize both results and show that the problem can be solved in polynomial time for S2,k,k-free subcubic graphs, for any fixed value of k.
This paper considers the global optimization of max-plus linear systems with affine equality constraints. For both the cases that the variables are real and non-negative, the necessary and sufficient ...conditions for the existence and uniqueness of globally optimal solutions are given, respectively. The proposed approaches are constructive and yield two polynomial algorithms for checking the solvabilities of the global optimization problems and finding all globally optimal solutions, in which the analytic expressions of general solutions are presented. The global optimization is then applied in the load scheduling of distributed systems with different processor capacities. The optimal allocation scheme is designed to minimize the completion time of the overall task. Some illustrative examples are presented to demonstrate the results.
PDF
