1,721,016 research outputs found
Distortion-Oblivious Algorithms for Minimizing Flow Time
Full text linkWe consider the classic online problem of scheduling on a single machine to minimize total flow time. In STOC 2021, the concept of robustness to distortion in processing times was introduced: for every distortion factor μ, an O(μ2)-competitive algorithm ALGμ which handles distortions up to μ was presented. However, using that result requires one to know the distortion of the input in advance, which is impractical.
We present the first \emph{distortion-oblivious} algorithms: algorithms which are competitive for \emph{every} input of \emph{every} distortion, and thus do not require knowledge of the distortion in advance. Moreover, the competitive ratios of our algorithms are Õ (μ), which is a quadratic improvement over the algorithm from STOC 2021, and is nearly optimal (we show a randomized lower bound of Ω(μ) on competitiveness)
Flow time scheduling with uncertain processing time
Full text linkWe consider the problem of online scheduling on a single machine in order to minimize weighted flow time. The existing algorithms for this problem (STOC ’01, SODA ’03, FOCS ’18) all require exact knowledge of the processing time of each job. This assumption is crucial, as even a slight perturbation of the processing time would lead to polynomial competitive ratio. However, this assumption very rarely holds in real-life scenarios.
In this paper, we present the first algorithm for weighted flow time which do not require exact knowledge of the processing times of jobs. Specifically, we introduce the Scheduling with Predicted Processing Time (SPPT) problem, where the algorithm is given a prediction for the processing time of each job, instead of its real processing time. For the case of a constant factor distortion between the predictions and the real processing time, our algorithms match all the best known competitiveness bounds for weighted flow time – namely O(logP), O(logD) and O(logW), where P,D,W are the maximum ratios of processing times, densities, and weights, respectively. For larger errors, the competitiveness of our algorithms degrades gracefully
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
No full textA semi-streaming algorithm in dynamic graph streams processes any n-vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph and using O (n · polylog(n )) space. Semi-streaming algorithms for dynamic streams were first obtained in the seminal work of Ahn, Guha, and McGregor in 2012, alongside the introduction of the graph sketching technique, which remains the de facto way of designing algorithms in this model and a highly popular technique for designing graph algorithms in general.We settle the pass complexity of approximating maximum matchings in dynamic streams via semistreaming algorithms by improving the state-of-the-art in both upper and lower bounds:• We present a randomized sketching based semi-streaming algorithm for O (1)-approximation of maximum matching in dynamic streams using O (log log n ) passes. The approximation ratio of this algorithm can be improved to (1 + ε ) for any fixed ε > 0 even on weighted graphs using standard techniques.This exponentially improves upon several O (log n ) pass algorithms developed for this problem since the introduction of the dynamic graph streaming model.• We prove that any semi-streaming algorithm (not only sketching based) for O (1)-approximation of maximum matching in dynamic streams requires Ω (log log n ) passes.This presents the first multi-pass lower bound for this problem, which is already also optimal, settling a longstanding open question in this area
Relating Interleaving and Fréchet Distances via Ordered Merge Trees
Full text linkMerge trees are a common topological descriptor for data with a hierarchical component, such as terrains and scalar fields. The interleaving distance, in turn, is a common distance for comparing merge trees. However, the interleaving distance for merge trees is solely based on the hierarchical structure, and disregards any other geometrical or topological properties that might be present in the underlying data. Furthermore, the interleaving distance is NP-hard to compute.In this paper, we introduce a form of ordered merge trees that can capture intrinsic order present in the data. We further define a natural variant of the interleaving distance, the monotone interleaving distance, which is an order-preserving distance for ordered merge trees. Analogously to the regular interleaving distance for merge trees, we show that the monotone variant has three equivalent definitions in terms of two maps, a single map, or a labelling. Furthermore, we establish a connection between the monotone interleaving distance of ordered merge trees and the Fréchet distance of 1D curves. As a result, the monotone interleaving distance between two ordered merge trees can be computed exactly in near-quadratic time in their complexity. The connection between the monotone interleaving distance and the Fréchet distance builds a new bridge between the fields of topological data analysis, where interleaving distances are a common tool, and computational geometry, where Fréchet distances are studied extensively
An LP-designed algorithm for constraint satisfaction
No full textThe class Max (r,2)-CSP consists of constraint satisfaction problems with at most two r-valued variables per clause. For instances with n variables and m binary clauses, we present an [(O)\tilde](r19m/100)O(r19m100) -time algorithm. It is the fastest algorithm for most problems in the class (including Max Cut and Max 2-Sat), and in combination with “Generalized CSPs” introduced in a companion paper, also allows counting, sampling, and the solution of problems like Max Bisection that escape the usual CSP framework. Linear programming is key to the design as well as the analysis of the algorithm
Approximating competitive equilibrium by Nash welfare
No full textWe explore the relationship between two popular concepts in the allocation of divisible items: competitive equilibrium(CE) and allocations that maximize Nash welfare, i.e., allocations where the weighted geometric mean of the utilities is maximal. When agents have homogeneous concave utility functions, these two concepts coincide: the classical Eisenberg–Gale convex program that maximizes Nash welfare over feasible allocations yields a competitive equilibrium. However,these two concepts diverge for non–homogeneous utilities. From a computational perspective, maximizing Nash welfare amounts to solving a convex program for any concave utility functions, whereas computing CE becomes PPAD-hard already for separable piecewise linear concave (SPLC) utilities.We introduce the concept of Gale-substitute utility functions, which is an analogue of the weak gross substitutes (WGS)property for the so-called Gale demand system. For Gale-substitutes utilities, we show that any allocation maximizing Nash welfare provides an approximate-CE with surprisingly strong guarantees, where every agent gets at least half the maximum utility they can get at any CE, and is approximately envy-free. Gale-substitutes include utility functions where computing CE is PPAD hard, such as all separable concave utilities and the previously studied non-separable class of Leontief-free utilities. We introduce a broad new class of utility functions called generalized network utilities based on the generalized flow model. This class includes SPLC and Leontief-free utilities, and we show that all such utilities are Gale-substitutes.Conversely, although some agents may get much higher utility at a Nash welfare maximizing allocation than at a CE,we show a price of anarchy type result: for general concave utilities, every CE achieves at least (1/e)1/e > 0.69 fraction of the maximum Nash welfare, and this factor is tight
Fully-Distributed Byzantine Agreement in Sparse Networks
Full text linkByzantine agreement is a fundamental problem in fault-tolerant distributed networks that has been studied intensively for the last four decades. Most of these works designed protocols for \emph{complete} networks. A key goal in Byzantine protocols is to tolerate as many Byzantine nodes as possible --- up to Byzantine nodes ( is the total network size). The work of Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] was the first to address the Byzantine agreement problem in \emph{sparse, bounded degree} networks and presented a protocol that achieved \emph{almost-everywhere} agreement among honest nodes. In such networks, all known Byzantine agreement protocols (e.g., Dwork, Peleg, Pippenger, and Upfal, STOC 1986; Upfal, PODC 1992; King, Saia, Sanwalani, and Vee, FOCS 2006) that tolerated a large number of Byzantine nodes had a major drawback that they were \emph{not fully-distributed} --- in those protocols, nodes are required to have initial knowledge of the entire network topolo
On estimating the trace of quantum state powers
Full text linkWe investigate the computational complexity of estimating the trace of quantum state powers tr(ρq) for an n-qubit mixed quantum state ρ, given its state-preparation circuit of size poly(n). This quantity is closely related to and often interchangeable with the Tsallis entropy Sq(ρ)=1−tr(ρq)q−1, where q=1 corresponds to the von Neumann entropy. For any non-integer q≥1+Ω(1), we provide a quantum estimator for Sq(ρ) with time complexity poly(n), exponentially improving the prior best results of exp(n) due to Acharya, Issa, Shende, and Wagner (ISIT 2019), Wang, Guan, Liu, Zhang, and Ying (TIT 2024), and Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (ESA 2024). Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation.Our quantum algorithm reveals a sharp phase transition between the case of q=1 and constant q>1 in the computational complexity of the Quantum q-Tsallis Entropy Difference Problem (TsallisQEDq), particularly deciding whether the difference Sq(ρ0)−Sq(ρ1) is at least 0.001 or at most −0.001:- For any 1+Ω(1)≤q≤2, TsallisQEDq is BQP-complete, which implies that Purity Estimation is also BQP-complete.- For any 1≤q≤1+1n−1, TsallisQEDq is QSZK-hard, leading to hardness of approximating von Neumann entropy because Sq(ρ)≤S(ρ), as long as BQP⊊QSZK.The hardness results are derived from reductions based on new inequalities for the quantum q-Jensen-(Shannon-)Tsallis divergence with 1≤q≤2, which are of independent interest
A topological proof of the Hell–Nešetřil dichotomy
No full textWe provide a new proof of a theorem of Hell and Nešetřil [J. Comb. Theory B, 48(1):92–110, 1990] using tools from topological combinatorics based on ideas of Lovász [J. Comb. Theory, Ser. A, 25(3):319–324, 1978]. The Hell–Nešetřil Theorem provides a dichotomy of the graph homomorphism problem. It states that deciding whether there is a graph homomorphism from a given graph to a fixed graph H is in P if H is bipartite (or contains a self-loop), and is NP-complete otherwise. In our proof we combine topological combinatorics with the algebraic approach to constraint satisfaction problem.</p
Partitioning a Polygon Into Small Pieces
No full textWe study the problem of partitioning a given simple polygon P into a minimum number of connected polygonal pieces, each of bounded size. We describe a general technique for constructing such partitions that works for several notions of ‘bounded size,’ namely that each piece must be contained in an axis-aligned or arbitrarily rotated unit square or a unit disk, or that each piece has bounded perimeter, straight-line diameter or geodesic diameter. The problems are motivated by practical settings in manufacturing, finite element analysis, collision detection, vehicle routing, shipping and laser capture microdissection.The version where each piece should be contained in an axis-aligned unit square is already known to be NP- hard [Abrahamsen and Stade, FOCS, 2024], and the other versions seem no easier. Our main result is to develop constant-factor approximation algorithms, which means that the number of pieces in the produced partition is at most a constant factor larger than the cardinality of an optimal partition. Existing algorithms [Damian and Pemmaraju, Algorithmica, 2004] do not allow Steiner points, which means that all corners of the produced pieces must also be corners of P. This has the disappointing consequence that a partition often does not exist, whereas our algorithms always produce meaningful partitions. Furthermore, an optimal partition without Steiner points may require Ω(n ) pieces for polygons with n corners where a partition consisting of just 2 pieces exists when Steiner points are allowed. Other existing algorithms [Arkin, Das, Gao, Goswami, Mitchell, Polishchuk and Tóth, ESA, 2020] only allow P to be split along chords (and aim to minimize the number of chords instead of the number of pieces), whereas we make no constraints on the boundaries of the pieces.In a related problem, we are given a polygon P and positive real values a1,…,ak whose sum equals the area of P. The goal is to partition P into exactly k pieces Q1,…, Qk such that the area of Qi is ai. Such a partition always exists, and an algorithm with running time O (nk) has previously been described [Bast and Hert, CCCG, 2000]. We improve on this result and give an algorithm with optimal running time O (n + k ) for simple polygons and a running time of O (n log n + k ) for polygons with holes
- …
