Publications related to Kruskal's algorithm

A continuum approximation approach to the depot location problem in a crowd-shipping system

Nikolaos Geroliminis, Patrick Stefan Adriaan Stokkink

Last-mile delivery in the logistics chain contributes to congestion in urban networks due to frequent stops. Crowd-shipping is a sustainable and low-cost alternative to traditional delivery but relies heavily on the availability of occasional couriers. In ...

PERGAMON-ELSEVIER SCIENCE LTD2023

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

EPFL2023

Frequency-Domain Non-intrusive Greedy Model Order Reduction Based on Minimal Rational Approximation

Fabio Nobile, Davide Pradovera

We present a technique for Model Order Reduction (MOR) of frequency-domain problems relying on rational interpolation of vector-valued functions. The selection of the sample points is carried out adaptively according to a greedy procedure. We describe seve ...

SPRINGER INTERNATIONAL PUBLISHING AG2021

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen

We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call o ...

2021

A comment on performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

Maryam Kamgarpour, Baiwei Guo, Orcun Karaca

We provide a counterexample to the performance guarantee obtained in the paper "Il'ev, V., Linker, N., 2006. Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid", which was published in Volume 171 of the Eur ...

ELSEVIER2021

Distributionally Robust Optimization with Markovian Data

Daniel Kuhn, Tobias Sutter, Mengmeng Li

We study a stochastic program where the probability distribution of the uncertain problem parameters is unknown and only indirectly observed via finitely many correlated samples generated by an unknown Markov chain with d states. We propose a data-driven d ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2021

MATHICSE Technical Report : Frequency-domain non-intrusive greedy Model Order Reduction based on minimal rational approximation

Fabio Nobile, Davide Pradovera

We present a technique for Model Order Reduction (MOR) of frequency-domain problems relying on rational interpolation of vector-valued functions. The selection of the sample points is carried out adaptively according to a greedy procedure. We describe seve ...

MATHICSE2020

A Homotopy Method with Adaptive Basis Selection for Computing Multiple Solutions of Differential Equations

Jan Sickmann Hesthaven

The homotopy continuation method has been widely used to compute multiple solutions of nonlinear differential equations, but the computational cost grows exponentially based on the traditional finite difference and finite element discretizations. In this w ...

SPRINGER/PLENUM PUBLISHERS2020

Two-step phase shifting interferometry based on orientation selective monogenic filtering

Pramod Rastogi, Rishikesh Dilip Kulkarni

We propose a phase step estimation algorithm in a two-step phase shifting interferometry setup based on orientation selective adaptive monogenic filtering (AMF). Initially, the AMF algorithm is used for the fringe pattern normalization. A minor modificatio ...

2019

Crowdsourcing with Fairness, Diversity and Budget Constraints

Boi Faltings, Naman Goel

Recent studies have shown that the labels collected from crowdworkers can be discriminatory with respect to sensitive attributes such as gender and race. This raises questions about the suitability of using crowdsourced data for further use, such as for tr ...

ASSOC COMPUTING MACHINERY2019

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

Christoph Hunkenschröder

We present a factors 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approxi ...

2019

The Sketching Complexity of Graph and Hypergraph Counting

Mikhail Kapralov, John Michael Goddard Kallaugher

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been ...

IEEE COMPUTER SOC2018

Testing Graph Clusterability: Algorithms and Lower Bounds

Mikhail Kapralov, Aidasadat Mousavifar, Ashish Hari Chiplunkar

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generali ...

IEEE COMPUTER SOC2018

Priority coordination of fiber positioners in multi-objects spectrographs

Denis Gillet, Jean-Paul Richard Kneib, Mohamed Bouri, Laleh Makarem

Projects such as "The Dark Energy Spectroscopic Instrument" (DESI) [1] or "The Multi Object Optical and Near-infrared Spectrograph" (MOONS) [5] are developing spectrographs, composed of more than thousand of optical fibers in a confined hexagonal focal pla ...

SPIE-INT SOC OPTICAL ENGINEERING2018

Reduced Numerical Approximation of Reduced Fluid-Structure Interaction Problems With Applications in Hemodynamics

Simone Deparis, Claudia Maria Colciago

This paper deals with fast simulations of the hemodynamics in large arteries by considering a reduced model of the associated fluid-structure interaction problem, which in turn allows an additional reduction in terms of the numerical discretisation. The re ...

2018

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Slobodan Mitrovic

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint

k

, with the added twist that a number of items

\tau

from the returned set may be removed. We focus on the worst-case setting considered in Orlin et al ...

2017

Spinner: Scalable Graph Partitioning in the Cloud

Andreas Loukas, Dionysios Logothetis

In this paper, we present a graph partitioning algorithm to partition graphs with trillions of edges. To achieve such scale, our solution leverages the vertex-centric Pregel abstraction provided by Giraph, a system for large-scale graph analytics. We desig ...

Ieee2017

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Justin Dean Ward

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a monotone increasing submodular function or ...

INFORMS2017

MINLP model and two-stage algorithm for the simultaneous synthesis of heat exchanger networks, utility systems and heat recovery cycles

François Maréchal, Alberto Mian, Emanuele Martelli

This work proposes a novel approach for the simultaneous synthesis of Heat Exchanger Networks (HEN) and Utility Systems of chemical processes and energy systems. Given a set of hot and cold process streams and a set of available utility systems, the method ...

2017

Maximizing k-Submodular Functions and Beyond

Justin Dean Ward

We consider the maximization problem in the value oracle model of functions defined on k-tuples of sets that are submodular in every orthant and r-wise monotone, where k >= 2 and 1

Assoc Computing Machinery2016