Search
Search Results
-
The Lower Bound for Koldobsky’s Slicing Inequality via Random Rounding
We study the lower bound for Koldobsky’s slicing inequality. We show that there exists a measure μ and a symmetric convex body $$K \subseteq...
-
SVD-based algorithms for fully-connected tensor network decomposition
The popular fully-connected tensor network (FCTN) decomposition has achieved successful applications in many fields. A standard method to this...
-
Maximum Coverage with Cluster Constraints: An LP-Based Approximation Technique
Packing problems constitute an important class of optimization problems. However, despite the large number of variants that have been studied in the...
-
An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
Relaxation and rounding approaches became a standard and extremely versatile tool for constrained submodular function maximization. One of the most...
-
LP-Based Algorithms for Multistage Minimization Problems
We consider a multistage framework introduced recently (Eisenstat et al., Gupta et al., both in ICALP 2014), where given a time horizon...
-
Private non-monotone submodular maximization
We propose a private algorithm for the problem of maximizing a submodular but not necessary monotone set function over a down-closed family of sets....
-
Practical Sketching Algorithms for Low-Rank Tucker Approximation of Large Tensors
Low-rank approximation of tensors has been widely used in high-dimensional data analysis. It usually involves singular value decomposition (SVD) of...
-
Hardness and approximation of submodular minimum linear ordering problems
The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum...
-
-
A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis
We consider the max hypergraph 3-cut problem with limited unbalance (MH3C-LU). The objective is to divide the vertex set of an edge-weighted...
-
-
Global Approximation of Local Optimality: Nonsubmodular Optimization
In the study of information technology, one of the important efforts is made on dealing with nonsubmodular optimizations since there are many such...
-
Approximate multi-matroid intersection via iterative refinement
We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns...
-
An approximation algorithm for the k-generalized Steiner forest problem
In this paper, we introduce the k -generalized Steiner forest ( k -GSF) problem, which is a natural generalization of the k -Steiner forest problem and...
-
Covariance’s Loss is Privacy’s Gain: Computationally Efficient, Private and Accurate Synthetic Data
The protection of private information is of vital importance in data-driven research, business and government. The conflict between privacy and...
-
Speed-robust scheduling: sand, bricks, and rocks
The speed-robust scheduling problem is a two-stage problem where, given m machines, jobs must be grouped into at most m bags while the processing...
-
Improved Online Algorithm for Fractional Knapsack in the Random Order Model
The fractional knapsack problem is one of the classical problems in combinatorial optimization, which is well understood in the offline setting....
-
-
Location of differentiated waste collection centers with user cooperation: a bilevel optimization approach
We focus on the problem of locating differentiated waste collection centers: a municipal firm acts with the goal of locating and installing proper...
-
The Mathematics of László Lovász
This is an exposition of the contributions of László Lovász to mathematics and computer science written on the occasion of the bestowal of the Abel...